2020/10/26 by Knor, Martin, Škrekovski, Riste, Tepeh, Aleksandra · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2010.13467
A set S of vertices in a graph G is a dominating set if every vertex of G is in S or is adjacent to a vertex in S. If, in addition, S is an independent set, then S is an independent dominating set. The domination number γ(G) of G is the minimum cardinality of a dominating set in G, while the independent domination number i(G) of G is the minimum cardinality of an independent dominating set in G. We prove that for all integers k ≥ 3 it holds that if G is a connected k-regular graph, then (i(G))/(γ(G)) ≤ (k)/(2), with equality if and only if G = Kk,k. The result was previously known only for k≤ 6. This affirmatively answers a recent question of Babikir and Henning.