Paper Info
Title
On A Conjecture On Total Domination In Claw-Free Cubic Graphs: Proof And New Upper Bound
Abstract
In 2008, Favaron and Henning proved that if G is a connected claw-free cubic graph of order n >= 10, then the total domination number gamma(t)(G) of G is at most 5/11 n, and they conjectured that in fact gamma(t)(G) is at most 4/9 n (see [O. Favaron and M.A. Henning, Discrete Math. 308 (2008), 3491-3507] and [M. A. Henning, Discrete Math. 309 (2009), 32-63]). In this paper, in a first step, we prove this conjecture and show that the bound is reached for exactly two graphs of order 18. In a second step, we prove that if G is a connected claw-free cubic graph of order n >= 20, then gamma(t)(G) = 10/23 n, and we show that this second bound is not reached. Henning and Southey (see [Discrete Math. 310 (2010), 2984-2999] also proved the initial conjecture, but in a less natural way. Moreover, they gave two graphs for which the bound is reached without proving that there are no others. An open problem is proposed in the last section.
Year
Venue
DocType
2011
AUSTRALASIAN JOURNAL OF COMBINATORICS
Journal
Volume
ISSN
Citations 
51
2202-3518
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Nicolas Lichiardopol111.02