2021/07/01 by Eun‐Kyung Cho, Cho, Eun-Kyung, Ilkyoo Choi +3
Computer Science · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2107.00295
openalex publication_date 2021/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 γ(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 Kk, k where k≥ 4. Generalizing a result by Lam, Shiu, and Sun, we prove that i(G)≤ (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 (i(G))/(γ(G)) ≤ (k3-3k2+2)/(2k2-6k+2), strengthening upon a result of Knor, Škrekovski, and Tepeh. In addition, we prove that a graph G' with maximum degree at most 4 satisfies i(G') ≤ (5)/(9)|V(G')|, which is also tight.