Premium
Domination versus independent domination in regular graphs
Author(s) -
Knor Martin,
Škrekovski Riste,
Tepeh Aleksandra
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22711
Subject(s) - dominating set , mathematics , combinatorics , domination analysis , vertex (graph theory) , maximal independent set , independent set , graph , discrete mathematics , cardinality (data modeling) , chordal graph , 1 planar graph , computer science , data mining
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, theni ( G )γ ( G )≤ k 2 , with equality if and only if G = K k , k . The result was previously known only for k ≤ 6 . This affirmatively answers a question of Babikir and Henning.