Bounds on total domination in claw-free cubic graphs

Odile Favaron, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)


A set S of vertices in a graph G is a total dominating set, denoted by TDS, of G if every vertex of G is adjacent to some vertex in S (other than itself). The minimum cardinality of a TDS of G is the total domination number of G, denoted by γt (G). If G does not contain K1, 3 as an induced subgraph, then G is said to be claw-free. It is shown in [D. Archdeacon, J. Ellis-Monaghan, D. Fischer, D. Froncek, P.C.B. Lam, S. Seager, B. Wei, R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004) 207-210.] that if G is a graph of order n with minimum degree at least three, then γt (G) ≤ n / 2. Two infinite families of connected cubic graphs with total domination number one-half their orders are constructed in [O. Favaron, M.A. Henning, C.M. Mynhardt, J. Puech, Total domination in graphs with minimum degree three, J. Graph Theory 34(1) (2000) 9-19.] which shows that this bound of n / 2 is sharp. However, every graph in these two families, except for K4 and a cubic graph of order eight, contains a claw. It is therefore a natural question to ask whether this upper bound of n / 2 can be improved if we restrict G to be a connected cubic claw-free graph of order at least 10. In this paper, we answer this question in the affirmative. We prove that if G is a connected claw-free cubic graph of order n ≥ 10, then γt (G) ≤ 5 n / 11.

Original languageEnglish
Pages (from-to)3491-3507
Number of pages17
JournalDiscrete Mathematics
Issue number16
Publication statusPublished - 28 Aug 2008
Externally publishedYes


  • Bounds
  • Claw-free cubic graphs
  • Total domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


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

Cite this