Name
Abstract | ||
|---|---|---|
Let G = (V, E) be a graph. A nonempty subset SV 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 ob- servation: 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 depthG(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 depthG(v) taken over v 2 V. We prove that depth(G) can be at most 1 4(3n 2 2n+3) and it can be computed in time O(n3). 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 rp(G) = IP{S contains an alliance}, with SV 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 |S| > n 2), then also rp(G) ! 1 as n ! 1. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-74456-6_21 | Mathematical Foundations of Computer Science |
Keywords | Field | DocType |
minimum distance,smallest alliance,polynomial time depthg,arbitrary node v,regular graph,time o,small alliance,value depth,planar regular graph,minimum degree,polynomial time,lower bound | Random regular graph,Discrete mathematics,Strongly regular graph,Combinatorics,Bound graph,Alliance,Degree (graph theory),Pathwidth,Time complexity,Mathematics,Bounded function | Conference |
Volume | ISSN | ISBN |
4708 | 0302-9743 | 3-540-74455-X |
Citations | PageRank | References |
6 | 0.71 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rodolfo Carvajal | 1 | 14 | 1.61 |
| Martín Matamala | 2 | 158 | 21.63 |
| Ivan Rapaport | 3 | 199 | 21.93 |
| Nicolas Schabanel | 4 | 341 | 27.82 |