×

zbMATH — the first resource for mathematics

Semitotal domination in claw-free cubic graphs. (English) Zbl 1354.05107
Summary: In this paper, we continue the study of semitotal domination in graphs in [the authors, Discrete Math. 324, 13–18 (2014; Zbl 1284.05196)]. A set \(S\) of vertices in \(G\) is a semitotal dominating set of \(G\) if it is a dominating set of \(G\) and every vertex in \(S\) is within distance 2 of another vertex of \(S\). The semitotal domination number, \(\gamma_{t2}(G)\), is the minimum cardinality of a semitotal dominating set of \(G\). This domination parameter is squeezed between arguably the two most important domination parameters; namely, the domination number, \(\gamma (G)\), and the total domination number, \(\gamma_{t}(G)\). We observe that \(\gamma (G) \leq \gamma_{t2}(G) \leq \gamma_{t}(G)\). A claw-free graph is a graph that does not contain \(K_{1,3}\) as an induced subgraph. We prove that if \(G\) is a connected, claw-free, cubic graph of order \(n \geq 10\), then \(\gamma_{t2}(G) \leq 4n/11\).

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chudnovsky, M.; Seymour, P., Claw-free graphs. V. global structure, J. Combin. Theory Ser. B, 98, 1373-1410, (2008) · Zbl 1196.05043
[2] Cockayne, E.J.; Favaron, O.; Mynhardt, C.M., Total domination in claw-free cubic graphs, J. Combin. Math. Combin. Comput., 43, 219-225, (2002) · Zbl 1011.05043
[3] Faudree, R.; Flandrin, E.; Ryjáček, Z., Claw-free graphs — a survey, Discrete Math., 164, 87-147, (1997) · Zbl 0879.05043
[4] Favaron, O.; Henning, M.A., Paired-domination in claw-free cubic graphs, Graphs Combin., 20, 447-456, (2004) · Zbl 1054.05074
[5] Favaron, O.; Henning, M.A., Total domination in claw-free graphs with minimum degree 2, Discrete Math., 308, 3213-3219, (2008) · Zbl 1158.05044
[6] Favaron, O.; Henning, M.A., Bounds on total domination in claw-free cubic graphs, Discrete Math., 308, 3491-3507, (2008) · Zbl 1190.05089
[7] Goddard, W.; Henning, M.A., Independent domination in graphs: a survey and recent results, Discrete Math., 313, 839-854, (2013) · Zbl 1260.05113
[8] Goddard, W.; Henning, M.A.; McPillan, C.A., Semitotal domination in graphs, Util. Math., 94, 67-81, (2014) · Zbl 1300.05220
[9] Haynes T.W., Hedetniemi S.T., Slater P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York (1998) · Zbl 0890.05002
[10] Haynes T.W., Hedetniemi S.T., Slater P.J.: Domination in Graphs: Advanced Topics. Marcel Dekker, Inc., New York (1998) · Zbl 0883.00011
[11] Haynes, T.W.; Henning, M.A.; Howard, J., Locating and total dominating sets in trees, Discrete Appl. Math., 154, 1293-1300, (2006) · Zbl 1091.05051
[12] Henning, M.A., A survey of selected recent results on total domination in graphs, Discrete Math., 309, 32-63, (2009) · Zbl 1219.05121
[13] Henning, M.A.; Kang, L.; Shan, E.; Yeo, A., On matching and total domination in graphs, Discrete Math., 308, 2313-2318, (2008) · Zbl 1145.05042
[14] Henning, M.A.; Löwenstein, C., Locating-total domination in claw-free cubic graphs, Discrete Math., 312, 3107-3116, (2012) · Zbl 1252.05162
[15] Henning, M.A.; Marcon, A.J., On matching and semitotal domination in graphs, Discrete Math., 324, 13-18, (2014) · Zbl 1284.05196
[16] Henning, M.A.; Marcon, A.J., Vertices contained in all or in no minimum semitotal dominating set of a tree, Discuss. Math. Graph Theory, 36, 71-93, (2016) · Zbl 1329.05232
[17] Henning, M.A.; Yeo, A., Hypergraphs with large transversal number and with edge sizes at least three, J. Graph Theory, 59, 326-348, (2008) · Zbl 1211.05091
[18] Henning M.A., Yeo A.: Total Domination in Graphs. Springer, New York (2013) · Zbl 1408.05002
[19] Lichiardopol, N., On a conjecture on total domination in claw-free cubic graphs: proof and new upper bound, Australas. J. Combin., 51, 7-28, (2011) · Zbl 1233.05149
[20] Southey, J.; Henning, M.A., On a conjecture on total domination in claw-free cubic graphs, Discrete Math., 310, 2984-2999, (2010) · Zbl 1222.05203
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.