Given a graph , a dominating set of is a set of vertices such that each vertex not in has a neighbor in . The domination number of , denoted , is the minimum size of a dominating set of . The independent domination number of , denoted , is the minimum size of a dominating set of 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 be a connected -regular graph that is not where $k\geq 4i(G)\le \frac{k-1}{2k-1}|V(G)|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 with maximum degree at most satisfies , which is also tight.

生成讲解博客的中文版本

生成AI智能校验的中文版本