Title of article :
Domination versus independent domination in cubic graphs
Author/Authors :
Southey، نويسنده , , Justin and Henning، نويسنده , , Michael A.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2013
Abstract :
A set S of vertices in a graph G is a dominating set if every vertex not in S 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 . In this paper we show that if G ≠ K ( 3 , 3 ) is a connected cubic graph, then i ( G ) / γ ( G ) ≤ 4 / 3 . This answers a question posed in Goddard (in press) [6] where the bound of 3 / 2 is proven. In addition we characterize the graphs achieving this ratio of 4 / 3 .
Keywords :
cubic graphs , Independent domination , domination , Ratio
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics