• Title of article

    Domination versus independent domination in cubic graphs

  • Author/Authors

    Southey، نويسنده , , Justin and Henning، نويسنده , , Michael A.، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2013
  • Pages
    9
  • From page
    1212
  • To page
    1220
  • 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
  • Serial Year
    2013
  • Journal title
    Discrete Mathematics
  • Record number

    1600322