Name
Abstract | ||
|---|---|---|
Let $$G$$G be a connected $$P_k$$Pk-free graph, $$k \ge 4$$k?4. We show that $$G$$G admits a connected dominating set that induces either a $$P_{k-2}$$Pk-2-free graph or a graph isomorphic to $$P_{k-2}$$Pk-2. In fact, every minimum connected dominating set of $$G$$G has this property. This yields a new characterization for $$P_k$$Pk-free graphs: a graph $$G$$G is $$P_k$$Pk-free if and only if each connected induced subgraph of $$G$$G has a connected dominating set that induces either a $$P_{k-2}$$Pk-2-free graph, or a graph isomorphic to $$C_k$$Ck. We present an efficient algorithm that, given a connected graph $$G$$G, computes a connected dominating set $$X$$X of $$G$$G with the following property: for the minimum $$k$$k such that $$G$$G is $$P_k$$Pk-free, the subgraph induced by $$X$$X is $$P_{k-2}$$Pk-2-free or isomorphic to $$P_{k-2}$$Pk-2. As an application our results, we prove that Hypergraph 2-Colorability can be solved in polynomial time for hypergraphs whose vertex-hyperedge incidence graphs is $$P_7$$P7-free.
|
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s00453-015-9989-6 | Algorithmica |
Keywords | DocType | Volume |
$$P_k$$Pk-free graph, 05C38, 05C69, 05C75, Computational complexity, Connected domination | Journal | 75 |
Issue | ISSN | Citations |
1 | 0178-4617 | 1 |
PageRank | References | Authors |
0.35 | 1 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eglantine Camby | 1 | 16 | 4.02 |
| Oliver Schaudt | 2 | 95 | 21.74 |