×

Bounds on total domination in claw-free cubic graphs. (English) Zbl 1190.05089

Summary: 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 \(\gamma _{t}(G)\). If \(G\) does not contain \(K_{1,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, and R. Yuster, “Some remarks on domination”, J. Graph Theory 46, No.3, 207–210 (2004; Zbl 1041.05057)] that if \(G\) is a graph of order \(n\) with minimum degree at least three, then \(\gamma _{t}(G)\leqslant 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, and J. Puech, “Total domination in graphs with minimum degree three”, J. Graph Theory 34, No.1, 9–19 (2000; Zbl 0945.05047)] which shows that this bound of \(n/2\) is sharp. However, every graph in these two families, except for \(K_{4}\) 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\geqslant \)10, then \(\gamma _{t}(G)\leqslant 5n/11\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Archdeacon, D.; Ellis-Monaghan, J.; Fischer, D.; Froncek, D.; Lam, P. C.B.; Seager, S.; Wei, B.; Yuster, R., Some remarks on domination, J. Graph Theory, 46, 207-210 (2004) · Zbl 1041.05057
[2] Biedl, T.; Demaine, E. D.; Duncan, C. A.; Fleischer, R.; Kobourov, S. G., Tight bounds on maximal and maximum matchings, Discrete Math., 285, 7-15 (2004) · Zbl 1044.05056
[3] Brigham, R. C.; Carrington, J. R.; Vitray, R. P., Connected graphs with maximum total domination number, J. Combin. Math. Combin. Comput., 34, 81-96 (2000) · Zbl 0958.05100
[4] Cockayne, E. J.; Dawes, R. M.; Hedetniemi, S. T., Total domination in graphs, Networks, 10, 211-219 (1980) · Zbl 0447.05039
[5] Favaron, O.; Henning, M. A., Paired domination in claw-free cubic graphs, Graphs Combin., 20, 447-456 (2004) · Zbl 1054.05074
[6] O. Favaron, M.A. Henning, Total domination in claw-free graphs with minimum degree two, Discrete Math., to appear.; O. Favaron, M.A. Henning, Total domination in claw-free graphs with minimum degree two, Discrete Math., to appear. · Zbl 1158.05044
[7] Favaron, O.; Henning, M. A.; Mynhardt, C. M.; Puech, J., Total domination in graphs with minimum degree three, J. Graph Theory, 34, 1, 9-19 (2000) · Zbl 0945.05047
[8] Flandrin, E.; Faudree, R.; Ryjáček, Z., Claw-free graphs—a survey, Discrete Math., 164, 87-147 (1997) · Zbl 0879.05043
[9] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.; T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998. · Zbl 0890.05002
[10] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs, Advanced Topics, Marcel Dekker, New York, 1998.; T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs, Advanced Topics, Marcel Dekker, New York, 1998. · Zbl 0883.00011
[11] Henning, M. A., Graphs with large total domination number, J. Graph Theory, 35, 1, 21-45 (2000) · Zbl 0959.05089
[12] M. A. Henning, A. Yeo, Hypergraphs with large transversal number and with edge sizes at least three, submitted for publication.; M. A. Henning, A. Yeo, Hypergraphs with large transversal number and with edge sizes at least three, submitted for publication. · Zbl 1211.05091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.