On independent domination of regular graphs

Abstract

Given a graph $G$, a dominating set of $G$ is a set $S$ of vertices such that each vertex not in $S$ has a neighbor in $S$. The domination number of $G$, denoted $\gamma (G)$, is the minimum size of a dominating set of $G$. The independent domination number of $G$, denoted $i(G)$, is the minimum size of a dominating set of $G$ that is also independent. Note that every graph has an independent dominating set, as a maximal independent set is equivalent to an independent dominating set. Let $G$ be a connected $k$-regular graph that is not $K_{k,k}$ where $k\ge 4$. Generalizing a result by Lam, Shiu, and Sun, we prove that $i(G)\le \frac{k-1}{2k-1}|V(G)|$, which is tight for $k=4$. This answers a question by Goddard et al. in the affirmative. We also show that $\frac{i(G)}{\gamma (G)}\le \frac{k^3-3k^2+2}{2k^2-6k+2}$, strengthening upon a result of Knor, Škrekovski, and Tepeh. In addition, we prove that a graph $G^{\prime }$ with maximum degree at most $4$ satisfies $i(G^{\prime })\le \frac{5}{9}|V(G^{\prime })|$, which is also tight.

15 pages, 5 figures