Geodesic
Total Forcing Sets and Zero Forcing Sets in Trees
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 733-754.

Voir la notice de l'article provenant de la source Library of Science

A dynamic coloring of the vertices of a graph G starts with an initial subset S of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is called a forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. If the initial set S has the added property that it induces a subgraph of G without isolated vertices, then S is called a total forcing set in G. The minimum cardinality of a total forcing set in G is its total forcing number, denoted F_t(G). We prove that if T is a tree of order n ≥ 3 with maximum degree Δ and with n_1 leaves, then n_1≤F_t(T)≤1/Δ((Δ-1)n+1). In both lower and upper bounds, we characterize the infinite family of trees achieving equality. Further we show that F_t(T) ≥ F (T) + 1, and we characterize the extremal trees for which equality holds.
Keywords: forcing set, forcing number, total forcing set, total forcing number 
@article{DMGT_2020_40_3_a2,
     author = {Davila, Randy and Henning, Michael A.},
     title = {Total {Forcing} {Sets} and {Zero} {Forcing} {Sets} in {Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {733--754},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a2/}
}
TY  - JOUR
AU  - Davila, Randy
AU  - Henning, Michael A.
TI  - Total Forcing Sets and Zero Forcing Sets in Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 733
EP  - 754
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a2/
LA  - en
ID  - DMGT_2020_40_3_a2
ER  - 
%0 Journal Article
%A Davila, Randy
%A Henning, Michael A.
%T Total Forcing Sets and Zero Forcing Sets in Trees
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 733-754
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a2/
%G en
%F DMGT_2020_40_3_a2
Davila, Randy; Henning, Michael A. Total Forcing Sets and Zero Forcing Sets in Trees. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 733-754. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a2/

[1] AIM Special Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008) 1628–1648. doi:10.1016/j.laa.2007.10.009

[2] 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. doi:10.1016/j.dam.2014.08.029

[3] F. Barioli, W. Barrett, S.M. Fallat, T. Hall, L. Hogben, B. Shader, P. van den Driessche and H. van der Holst, Parameters related to tree-width, zero forcing, and maximum nullity of a graph, J. Graph Theory 72 (2013) 146–177. doi:10.1002/jgt.21637

[4] D. Burgarth, V. Giovannetti, L. Hogben, S. Severini and M. Young, Logic circuits from zero forcing, Nat. Comput. 14 (2015) 485–490. doi:10.1007/s11047-014-9438-5

[5] B. Brimkov and I.V. Hicks, Complexity and computation of connected zero forcing, Discrete Appl. Math. 229 (2017) 31–45. doi:10.1016/j.dam.2017.05.016

[6] Y. Caro and R. Pepper, Dynamic approach to k-forcing, Theory Appl. Graphs 2(2) (2015) Article 2.

[7] C. Chekuri and N. Korula, A graph reduction step preserving element-connectivity and applications, Automata, Languages and Programming, Springer (2009) 254–265.

[8] R. Davila, Bounding the Forcing Number of a Graph, Masters Thesis (Rice University, 2015).

[9] R. Davila and M.A. Henning, The forcing number of graphs with a given girth, Quaest. Math. 41 (2018) 189–204. doi:10.2989/16073606.2017.1376230

[10] R. Davila and M.A. Henning, On the total forcing number of a graph, manuscript (2017). arXiv:1702.06035

[11] R. Davila and F. Kenter, Bounds for the zero forcing number of a graph with large girth, Theory Appl. Graphs 2 (2015) Article 1.

[12] C. Edholm, L. Hogben, J. LaGrange and D. Row, Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph, Linear Algebra Appl. 436 (2012) 4352–4372. doi:10.1016/j.laa.2010.10.015

[13] D.K. Garnick, Y.H. Harris Kwong and F. Lazebnik, Extremal graphs without three-cycles or four-cycles, J. Graph Theory 17 (1993) 633–645. doi:10.1002/jgt.3190170511

[14] 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. doi:10.1016/j.dam.2016.06.004

[15] M. Gentner and D. Rautenbach, Some bounds on the zero forcing number of a graph, Discrete Appl. Math. 236 (2018) 203–213. doi:10.1016/j.dam.2017.11.015

[16] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Decker, Inc., NY, 1998).

[17] T.W. Haynes, S.T. Hedetniemi, S.T. Hedetniemi and M.A. Henning, Domination in graphs applied to electric power networks, SIAM J. Discrete Math. 15 (2002) 519–529. doi:10.1137/S0895480100375831

[18] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013). doi:10.1007/978-1-4614-6525-6

[19] L. Hogben, M. Huynh, N. Kingsley, S. Meyer, S. Walker and M. Young, Propagation time for zero forcing on a graph, Discrete Appl. Math. 160 (2012) 1994–2005. doi:10.1016/j.dam.2012.04.003

[20] L. Lu, B. Wu and Z. Tang, Proof of a conjecture on the zero forcing number of a graph, Discrete Appl. Math. 213 (2016) 233–237. doi:10.1016/j.dam.2016.05.009

[21] O. Ore, Theory of Graphs (Amer. Math. Soc., Providence, RI, 1962). doi:10.1090/coll/038

[22] M. Trefois and J.C. Delvenne, Zero forcing number, constrained matchings and strong structural controllability, Linear Algebra Appl. 484 (2015) 199–218. doi:10.1016/j.laa.2015.06.025