On a conjecture about inverse domination in graphs
Allan Frendrup, Michael A. Henning, Bert Randerath, Preben Dahl Vestergaard · 2010
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′ ⊆ 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.