Independent Domination in Cubic Graphs

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 not equal C5 K2 is a connected cubic graph of order n that does not have a subgraph isomorphic to K2,3, then i ( G) < 3n/ 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) = 3n/ 8, where. ( G) denotes the domination number of G. (c) 2015 Wiley Periodicals, Inc. J. Graph Theory 80: 329- 349, 2015