Article in press
Authors:
Title:
Semitotal forcing in claw-free cubic graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-11-11 , Revised: 2023-05-21 , Accepted: 2023-05-25 , Available online: 2023-06-19 , https://doi.org/10.7151/dmgt.2501
Abstract:
For an isolate-free graph $G=(V(G),E(G))$, a set $S\subseteq V(G)$ is called a
semitotal forcing set of $G$ if it is a forcing set (or a zero forcing set)
of $G$ and every vertex in $S$ is within distance 2 of another vertex of $S$.
The semitotal forcing number $F_{t2}(G)$ is the minimum cardinality of a
semitotal forcing set in $G$. In this paper, we prove that if $G \neq K_4$ is
a connected claw-free cubic graph of order $n$, then $F_{t2}(G)\leq
\frac{3}{8}n+1$. The graphs achieving equality in this bound are characterized,
an infinite set of graphs.
Keywords:
semitotal forcing number, claw-free, cubic
References:
- A. Aazami, Hardness Results and Approximation Algorithms for Some Problems on Graphs, Ph.D. Thesis (University of Waterloo, 2008).
- AIM Minimum Rank-Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler, S.M. Cioabǎ, D. Cvetković, S.M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanović, H. van der Holst, K. Vander Meulen and A. Wangsness Wehe), Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008) 1628–1648.
https://doi.org/10.1016/j.laa.2007.10.009 - D. Amos, Y. Caro, R. Davila and R. Pepper, Upper bounds on the $k$-forcing number of a graph, Discrete Appl. Math. 181 (2015) 1–10.
https://doi.org/10.1016/j.dam.2014.08.029 - D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Phys. Rev. Lett. 99 (2007) 100501.
https://doi.org/10.1103/PhysRevLett.99.100501 - D. Burgarth, V. Giovannetti, L. Hogben, S. Severini and M. Young, Logic circuits from zero forcing, Nat. Comput. 14 (2015) 485–490.
https://doi.org/10.1007/s11047-014-9438-5 - C. Chekuri and N. Korula, A graph reduction step preserving element-connectivity and applications, in: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 5555, (Springer 2009) 254–265.
https://doi.org/10.1007/978-3-642-02927-1_22 - Q. Chen, On the semitotal forcing number of a graph, Bull. Malays. Math. Sci. Soc. 45 (2022) 1409–1424.
https://doi.org/10.1007/s40840-021-01236-2 - R. Davila and M.A. Henning, Total forcing and zero forcing in claw-free cubic graphs, Graphs Combin. 34 (2018) 1371–1384.
https://doi.org/10.1007/s00373-018-1934-4 - R. Davila and M.A. Henning, Total forcing versus total domination in cubic graphs, Appl. Math. Comput. 354 (2019) 385–395.
https://doi.org/10.1016/j.amc.2019.02.060 - R. Davila and M.A. Henning, On the total forcing number of a graph, Discrete Appl. Math. 257 (2019) 115–127.
https://doi.org/10.1016/j.dam.2018.09.001 - R. Davila and M.A. Henning, Zero forcing in claw-free cubic graphs, Bull. Malays. Math. Sci. Soc. 43 (2020) 673–688.
https://doi.org/10.1007/s40840-018-00705-5 - M. Fürst and D. Rautenbach, A short proof for a lower bound on the zero forcing number, Discuss. Math. Graph Theory 40 (2020) 355–360.
https://doi.org/10.7151/dmgt.2117 - M. Gentner, L.D. Penso, D. Rautenbach and U.S. Souza, Extremal values and bounds for the zero forcing number, Discrete Appl. Math. 214 (2016) 196–200.
https://doi.org/10.1016/j.dam.2016.06.004 - M. Gentner and D. Rautenbach, Some bounds on the zero forcing number of a graph, Discrete Appl. Math. 236 (2018) 203–213.
https://doi.org/10.1016/j.dam.2017.11.015 - M. He and S. Ji, Note on forcing problem of trees, Graphs Combin. 38 (2022) 3.
https://doi.org/10.1007/s00373-021-02402-w - M. Henning and C. Löwenstein, Locating-total domination in claw-free cubic graphs, Discrete Math. 312 (2012) 3107–3116.
https://doi.org/10.1016/j.disc.2012.06.024 - H. Jiang, W. Li and J. Zhang, On trees and unicyclic graphs with equal forcing-type numbers, Bull. Malays. Math. Sci. Soc. 45 (2022) 1607–1620.
https://doi.org/10.1007/s40840-022-01276-2 - S. Li and W. Sun, On the zero forcing number of a graph involving some classical parameters, J. Comb. Optim. 39 (2020) 365-384.
https://doi.org/10.1007/s10878-019-00475-1 - Y.-P. Liang, J. Li and S.-J. Xu, On extremal graphs for zero forcing number, Graphs Combin. 38 (2022) 185.
https://doi.org/10.1007/s00373-022-02591-y - Y.-P. Liang and S.-J. Xu, On graphs maximizing the zero forcing number, Discrete Appl. Math. 334 (2023) 81–90.
https://doi.org/10.1016/j.dam.2023.03.011 - L. Lu, B. Wu and Z. Tang, Proof of a conjecture on the zero forcing number of a graph, Discrete Appl. Math. 213 (2016) 223–237.
https://doi.org/10.1016/j.dam.2016.05.009 - N. Monshizadeh, S. Zhang and M.K. Camlibel, Zero forcing sets and controllability of dynamical systems defined on graphs, IEEE Trans. Automat. Control 59 (2014) 2562–2567.
https://doi.org/10.1109/TAC.2014.2308619 - D.D. Row, A technique for computing the zero forcing number of a graph with a cut-vertex, Linear Algebra Appl. 436 (2012) 4423–4432.
https://doi.org/10.1016/j.laa.2011.05.012 - X. Wang, D. Wong and Y. Zhang, Zero forcing number of a graph in terms of the number of pendant vertices, Linear Multilinear Algebra 68 (2020) 1424–1433.
https://doi.org/10.1080/03081087.2018.1545829
Close