Abstract
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 paper, we study the following conjecture posed by Goddard and Henning (Discrete Math. 313:839–854, 2013): If G≇ K3 , 3 is a connected, cubic, bipartite graph on n vertices, then i(G)≤411n. Henning et al. (Discrete Appl. Math. 162:399–403, 2014) prove the conjecture when the girth is at least 6. In this paper we strengthen this result by proving the conjecture when the graph has no subgraph isomorphic to K2 , 3.
Original language | English |
---|---|
Pages (from-to) | 881-912 |
Number of pages | 32 |
Journal | Graphs and Combinatorics |
Volume | 35 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1 Jul 2019 |
Keywords
- Cubic Graphs
- Domination
- Independent Domination
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics