Independent Domination in Cubic Graphs
Prof Michael Henning, University of Johannesburg
Friday, 1 March 2013, 13h00, M 304
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. Let G be a connected cubic graph of order n. We present two results. The first result is that if G does not have a subgraph isomorphic to K2,3, then i(G) ≤ 3n/8. The second result is that if G is bipartite and with no 4-cycle, then i(G) ≤ 4n/11.