Abstract
Let G = (V, E) be a graph with no isolated vertex. A classical observation in domination theory is that if D is a minimum dominating set of G, then V \ D is also a dominating set of G. A set D' is an inverse dominating set of G if D' is a dominating set of G and D' subset of V \ D for some minimum dominating set D of G. The inverse domination number of G is the minimum cardinality among all inverse dominating sets of G. The independence number of G is the maximum cardinality of an independent set of vertices in G. Domke, Dunbar, and Markus (Ars Combin. 72 (2004), 149-160) conjectured that the inverse domination number of G is at most the independence number of G. We prove this conjecture for special families of graphs, including claw-free graphs, bipartite graphs, split graphs, very well covered graphs, chordal graphs and cactus graphs.
Original language | English |
---|---|
Journal | Ars Combinatoria |
Volume | 97A |
Pages (from-to) | 129-143 |
Number of pages | 15 |
ISSN | 0381-7032 |
Publication status | Published - 2010 |