On independent domination of regular graphs
Eun‐Kyung Cho, Ilkyoo Choi, Boram Park
Abstract
Abstract The domination number of a graph , denoted , is the minimum size of a dominating set of , and the independent domination number of , denoted , is the minimum size of a dominating set of that is also independent. Let be an integer. Generalizing a result on cubic graphs by Lam, Shiu, and Sun, we prove that for a connected ‐regular graph that is not , which is tight for . This answers a question by Goddard et al. in the affirmative. We also show that for a connected ‐regular graph that is not , strengthening upon a result of Knor, Škrekovski, and Tepeh. In addition, we prove that a graph with maximum degree at most 4 satisfies , which is also tight.
Topics & Concepts
MathematicsCombinatoricsDominating setDomination analysisGraphCubic graphDiscrete mathematicsLine graphVoltage graphVertex (graph theory)Advanced Graph Theory ResearchLimits and Structures in Graph TheoryComplexity and Algorithms in Graphs