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 $kgeq 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, v{S}krekovski, and Tepeh. In addition, we prove that a graph $G$ with maximum degree at most $4$ satisfies $i(G) le frac{5}{9}|V(G)|$, which is also tight.
تحميل البحث