Hereditary Efficiently Dominatable Graphs |
| |
Authors: | Martin Milanič |
| |
Affiliation: | UNIVERSITY OF PRIMORSKA, , SI6000 KOPER, SLOVENIA |
| |
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: | perfect code efficient domination perfect domination hereditary graph class hereditary efficiently dominatable graph forbidden induced subgraph characterization |
|
|