Small Alliances in Graphs Export

@incollection{citeulike:1624759, abstract = {Let G = (V,E) be a graph. A nonempty subset S ⊆ V is a (strong defensive) alliance of G if every node in S has at least as many neighbors in S than in V ∖ S. This work is motivated by the following observation: when G is a locally structured graph its nodes typically belong to small alliances. Despite the fact that finding the smallest alliance in a graph is NP-hard, we can at least compute in polynomial time depth G (v), the minimum distance one has to move away from an arbitrary node v in order to find an alliance containing v. We define depth(G) as the sum of depth G (v) taken over v ∈ V. We prove that depth(G) can be at most and it can be computed in time O(n 3). Intuitively, the value depth(G) should be small for clustered graphs. This is the case for the plane grid, which has a depth of 2n. We generalize the previous for bridgeless planar regular graphs of degree 3 and 4. The idea that clustered graphs are those having a lot of small alliances leads us to analyze the value of {S contains an alliance}, with S ⊆ V randomly chosen. This probability goes to 1 for planar regular graphs of degree 3 and 4. Finally, we generalize an already known result by proving that if the minimum degree of the graph is logarithmically lower bounded and if S is a large random set (roughly , then also r p (G) →1 as n → ∞.}, author = {Carvajal, Rodolfo and Matamala, Mart\'{\i}n and Rapaport, Ivan and Schabanel, Nicolas}, citeulike-article-id = {1624759}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-74456-6_21}, doi = {10.1007/978-3-540-74456-6_21}, journal = {Mathematical Foundations of Computer Science 2007}, keywords = {alliances, clustering, coefficient, graphs, network}, pages = {218--227}, posted-at = {2007-09-05 19:15:41}, priority = {5}, title = {Small Alliances in Graphs}, url = {http://dx.doi.org/10.1007/978-3-540-74456-6_21}, year = {2007} }

TY - CHAP ID - citeulike:1624759 L3 - citeulike-article-id:1624759 N2 - Let G = (V,E) be a graph. A nonempty subset S ⊆ V is a (strong defensive) alliance of G if every node in S has at least as many neighbors in S than in V ∖ S. This work is motivated by the following observation: when G is a locally structured graph its nodes typically belong to small alliances. Despite the fact that finding the smallest alliance in a graph is NP-hard, we can at least compute in polynomial time depth G (v), the minimum distance one has to move away from an arbitrary node v in order to find an alliance containing v. We define depth(G) as the sum of depth G (v) taken over v ∈ V. We prove that depth(G) can be at most and it can be computed in time O(n 3). Intuitively, the value depth(G) should be small for clustered graphs. This is the case for the plane grid, which has a depth of 2n. We generalize the previous for bridgeless planar regular graphs of degree 3 and 4. The idea that clustered graphs are those having a lot of small alliances leads us to analyze the value of {S contains an alliance}, with S ⊆ V randomly chosen. This probability goes to 1 for planar regular graphs of degree 3 and 4. Finally, we generalize an already known result by proving that if the minimum degree of the graph is logarithmically lower bounded and if S is a large random set (roughly , then also r p (G) →1 as n → ∞. JF - Mathematical Foundations of Computer Science 2007 EP - 227 TI - Small Alliances in Graphs SP - 218 KW - alliances KW - clustering KW - coefficient KW - graphs KW - network AU - Carvajal, Rodolfo AU - Matamala, Martín AU - Rapaport, Ivan AU - Schabanel, Nicolas PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-74456-6_21 ER -