Geodesic
Semitotal forcing in claw-free cubic graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1373-1393 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

For an isolate-free graph G=(V(G),E(G)), a set S⊆ 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 K_4 is a connected claw-free cubic graph of order n, then F_t2(G)≤38n+1. The graphs achieving equality in this bound are characterized, an infinite set of graphs.
Keywords: semitotal forcing number, claw-free, cubic 
@article{DMGT_2024_44_4_a8,
     author = {Liang, Yi-Ping and Chen, Jie and Xu, Shou-Jun},
     title = {Semitotal forcing in claw-free cubic graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1373--1393},
     year = {2024},
     volume = {44},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a8/}
}
TY  - JOUR
AU  - Liang, Yi-Ping
AU  - Chen, Jie
AU  - Xu, Shou-Jun
TI  - Semitotal forcing in claw-free cubic graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1373
EP  - 1393
VL  - 44
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a8/
LA  - en
ID  - DMGT_2024_44_4_a8
ER  - 
%0 Journal Article
%A Liang, Yi-Ping
%A Chen, Jie
%A Xu, Shou-Jun
%T Semitotal forcing in claw-free cubic graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1373-1393
%V 44
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a8/
%G en
%F DMGT_2024_44_4_a8
Liang, Yi-Ping; Chen, Jie; Xu, Shou-Jun. Semitotal forcing in claw-free cubic graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1373-1393. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a8/

[1] A. Aazami, Hardness Results and Approximation Algorithms for Some Problems on Graphs, Ph.D. Thesis (University of Waterloo, 2008).

[2] 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

[3] 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

[4] 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

[5] 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

[6] 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

[7] 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

[8] 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

[9] 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

[10] 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

[11] 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

[12] 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

[13] 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

[14] 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

[15] 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

[16] 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

[17] 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

[18] 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

[19] 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

[20] 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

[21] 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

[22] 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

[23] 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

[24] 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