Premium
Independent Domination in Cubic Graphs
Author(s) -
Dorbec Paul,
Henning Michael A.,
Montassier Mickael,
Southey Justin
Publication year - 2015
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.21855
Subject(s) - combinatorics , mathematics , dominating set , vertex (graph theory) , cubic graph , domination analysis , graph , induced subgraph , independent set , discrete mathematics , line graph , voltage graph
A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S . The independent domination number of G , denoted by i ( G ) , is the minimum cardinality of an independent dominating set. In this article, we show that if G ≠ C 5□K 2is a connected cubic graph of order n that does not have a subgraph isomorphic to K 2, 3 , then i ( G ) ≤ 3 n / 8 . As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277–295] that if G is a cubic graph of order n , then γ ( G ) ≤ 3 n / 8 , where γ ( G ) denotes the domination number of G .