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.
|Number of pages||15|
|Publication status||Published - 2010|