Abstract
A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, S is an independent set, then S is an independent dominating set. The domination number γ(G) of G is the minimum cardinality of a dominating set in G, while the independent domination number i(G) of G is the minimum cardinality of an independent dominating set in G. In this paper we show that if G≠K(3,3) is a connected cubic graph, then i(G)/γ(G)≤4/3. This answers a question posed in Goddard (in press) [6] where the bound of 3/2 is proven. In addition we characterize the graphs achieving this ratio of 4/3.
Original language | English |
---|---|
Pages (from-to) | 1212-1220 |
Number of pages | 9 |
Journal | Discrete Mathematics |
Volume | 313 |
Issue number | 11 |
DOIs | |
Publication status | Published - 2013 |
Keywords
- Cubic graphs
- Domination
- Independent domination
- Ratio
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics