On a problem of Domke, Dunbar, Haynes, Hedetniemi, and Markus Concerning the inverse Domination number

Abstract

The problem of the title is: can the inverse domination number of a finite simple graph with no isolated vertices ever exceed its vertex independence number? We consider a related problem: which graphs contain a minimum dominating set and a maximal independent set which are disjoint? Main results: among graphs with domination number ≤ 4, the answer to the first question is no, and among graphs with domination number ≤ 2, there is such a pair of sets as called for in the second question unless the graph is K_m,n for some m,n ≥ 3.

Keywords:

• domination
• domination number
• inverse domination number
• independent set
• independence number

2010 Mathematics Subject Classification:

• 05C69