Hereditary Efficiently Dominatable Graphs
Open Access
- 16 July 2012
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 73 (4) , 400-424
Abstract
An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. We introduce graphs that are hereditary efficiently dominatable in that sense that every induced subgraph of the graph contains an efficient dominating set. We prove a decomposition theorem for (bull, fork, C4)‐free graphs, based on which we characterize, in terms of forbidden induced subgraphs, the class of hereditary efficiently dominatable graphs. We also give a decomposition theorem for hereditary efficiently dominatable graphs and examine some algorithmic aspects of such graphs. In particular, we give a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs by reducing the problem to the maximum weight independent set problem in claw‐free graphs.Keywords
This publication has 39 references indexed in Scilit:
- The structure of bull-free graphs I—Three-edge-paths with centers and anticentersJournal of Combinatorial Theory, Series B, 2012
- The structure of bull-free graphs II and III—A summaryJournal of Combinatorial Theory, Series B, 2012
- Stability number of bull- and chair-free graphs revisitedDiscrete Applied Mathematics, 2003
- A Theorem of TruemperCombinatorica, 2000
- Weighted domination of cocomparability graphsDiscrete Applied Mathematics, 1997
- Universally signable graphsCombinatorica, 1997
- The weighted perfect domination problem and its variantsDiscrete Applied Mathematics, 1996
- Weighted independent perfect domination on cocomparability graphsDiscrete Applied Mathematics, 1995
- Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphsInformation Processing Letters, 1993
- Trivially perfect graphsDiscrete Mathematics, 1978