On independent domination of regular graphs - Cho, Eun Kyung; Choi, Ilkyoo; Park, Boram (Journal of Graph Theory, 2023)
The domination number of a graph (Formula presented.), denoted (Formula presented.), is the minimum size of a dominating set of (Formula presented.), and the independent domination number of (Formula presented.), denoted (Formula presented.), is the minimum size of a dominating set of (Formula presented.) that is also independent. Let (Formula presented.) be an integer. Generalizing a result on cubic graphs by Lam, Shiu, and Sun, we prove that (Formula presented.) for a connected (Formula presented.) -regular graph (Formula presented.) that is not (Formula presented.), which is tight for (Formula presented.). This answers a question by Goddard et al. in the affirmative. We also show that (Formula presented.) for a connected (Formula presented.) -regular graph (Formula presented.) that is not (Formula presented.), strengthening upon a result of Knor, Škrekovski, and Tepeh. In addition, we prove that a graph (Formula presented.) with maximum degree at most 4 satisfies (Formula presented.), which is also tight.
Keywords: Cubic graph; Dominating sets; Domination; Domination number; Independent domination number; Independent dominations; Maximum degree; Regular graphs; domination; independent domination; regular graphs