On a conjecture on total domination in claw-free cubic graphs

Justin Southey, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

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 languageEnglish
Pages (from-to)2984-2999
Number of pages16
JournalDiscrete Mathematics
Volume310
Issue number21
DOIs
Publication statusPublished - 6 Nov 2010

Keywords

  • Bounds
  • Claw-free cubic graphs
  • Discharging rules
  • Total domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On a conjecture on total domination in claw-free cubic graphs'. Together they form a unique fingerprint.

Cite this