Article in press
Authors:
Title:
Semitotal domination in claw-free graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-02-07 , Revised: 2023-07-20 , Accepted: 2023-07-21 , Available online: 2023-09-02 , https://doi.org/10.7151/dmgt.2512
Abstract:
In an isolate-free graph $G$, a subset $S$ of vertices 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 of $G$, denoted by $\gamma_{t2}(G)$, is the minimum cardinality of a
semitotal dominating set in $G$. We prove that if $G$ is a connected claw-free
graph of order $n$ with minimum degree $\delta(G)\geqslant 2$ and is not one of
fourteen exceptional graphs (ten of which are cycles), then $\gamma_{t2}(G)
\leqslant \frac{3}{7}n$, and we also characterize the graphs achieving equality,
which are an infinite family of graphs. In particular, if we restrict $\delta(G)
\geqslant 3$ and $G\neq K_4$, then we can improve the result to $\gamma_{t2}(G)
\leqslant \frac{2}{5}n$, solving the conjecture for the case of claw-free graphs,
proposed by Goddard, Henning and McPillan in
[Semitotal domination in graphs,
Util. Math. 94 (2014) 67–81].
Keywords:
semitotal domination, minimum degree, claw-free graphs
References:
- J. Chen and S.-J. Xu, A characterization of $3$-$\gamma$-critical graphs which are not bicri-tical, Inform. Process. Lett. 166 (2021) 106062.
https://doi.org/10.1016/j.ipl.2020.106062 - Y. Dong, E. Shan, L. Kang and S. Li, Domination in intersecting hypergraphs, Discrete Appl. Math. 251 (2018) 155–159.
https://doi.org/10.1016/j.dam.2018.05.039 - W. Goddard, M.A. Henning and C.A. McPillan, Semitotal domination in graphs, Util. Math. 94 (2014) 67-81.
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (CRC Press, Boca Raton, 1998).
https://doi.org/10.1201/9781482246582 - M.A. Henning and A. Yeo, Total Domination in Graphs (Springer, New York, 2013).
https://doi.org/10.1007/978-1-4614-6525-6 - M.A. Henning, Bounds on domination parameters in graphs: a brief survey, Discuss. Math. Graph Theory 42 (2022) 665–708.
https://doi.org/10.7151/dmgt.2454 - M.A. Henning and A.J. Marcon, On matching and semitotal domination in graphs, Discrete Math. 324 (2014) 13–18.
https://doi.org/10.1016/j.disc.2014.01.021 - M.A. Henning, Edge weighting functions on semitotal dominating sets, Graphs Combin. 33 (2017) 403–417.
https://doi.org/10.1007/s00373-017-1769-4 - M.A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs, Theoret. Comput. Sci. 766 (2019) 46–57.
https://doi.org/10.1016/j.tcs.2018.09.019 - E. Zhu, Z. Shao and J. Xu, Semitotal domination in claw-free cubic graphs, Graphs Combin. 33 (2017) 1119–1130.
https://doi.org/10.1007/s00373-017-1826-z
Close