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 inS. The independent domination number of G, denoted by, is the minimum cardinality of an independent dominating set. In this article, we show that if is a connected cubic graph of ordern that does not have a subgraph isomorphic to K2, 3, then . As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277295] that if G is a cubic graph of ordern, then , where denotes the domination number of G.
independent domination number domination number cubic graphs 05c69