On a Conjecture about Inverse Domination in Graphs

Allan Frendrup, Michael A. Henning, Bert Randerath, Preben D. Vestergaard

Research output: Contribution to journalJournal articleResearchpeer-review

4 Citations (Scopus)


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 languageEnglish
JournalArs Combinatoria
Pages (from-to)129-143
Number of pages15
Publication statusPublished - 2010

Cite this

Frendrup, A., Henning, M. A., Randerath, B., & Vestergaard, P. D. (2010). On a Conjecture about Inverse Domination in Graphs. Ars Combinatoria, 97A, 129-143.