Abstract
In an earlier manuscript [O. Favaron, M.A. Henning, Bounds on total domination in clawfree cubic graphs, Discrete Math. 308 (2008) 3491-3507] it is shown that if G is a connected claw-free cubic graph of order n ≥ 10, then γt (G) ≤ 5n/11 and it is conjectured that the bound can be improved from 5n/11 to 4n/9. In this paper, we prove this conjecture. Our proof assigns weights to the edges and uses discharging rules to determine the average sum of the edge weights incident to each vertex, and then uses counting arguments to establish the desired upper bound.
Original language | English |
---|---|
Pages (from-to) | 2984-2999 |
Number of pages | 16 |
Journal | Discrete Mathematics |
Volume | 310 |
Issue number | 21 |
DOIs | |
Publication status | Published - 6 Nov 2010 |
Keywords
- Bounds
- Claw-free cubic graphs
- Discharging rules
- Total domination
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics