Article in volume
Authors:
Title:
Zero and total forcing dense graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(3) (2023) 619-634
Received: 2020-03-20 , Revised: 2020-12-09 , Accepted: 2020-12-12 , Available online: 2021-01-07 , https://doi.org/10.7151/dmgt.2389
Abstract:
If $S$ is a set of colored vertices in a simple graph $G$, then one may allow
a colored vertex with exactly one non-colored neighbor to force its non-colored
neighbor to become colored. If by iteratively applying this color change rule,
all of the vertices in $G$ become colored, then $S$ is a zero forcing set of $G$.
The minimum cardinality of a zero forcing set in $G$, written $Z(G)$, is the
zero forcing number of $G$. If in addition, $S$ induces a subgraph of $G$
without isolated vertices, then $S$ is a total forcing set of $G$. The total
forcing number of $G$, written $F_t(G)$, is the minimum cardinality of a total
forcing set in $G$. In this paper we introduce, and study, the notion of graphs
for which all vertices are contained in some minimum zero forcing set, or some
minimum total forcing set; we call such graphs ZF-dense and TF-dense,
respectively. A graph is ZTF-dense if it is both ZF-dense and TF-dense.
We determine various classes of ZTF-dense graphs, including among others,
cycles, complete multipartite graphs of order at least three that are not stars,
wheels, $n$-dimensional hypercubes, and diamond-necklaces. We show that no tree
of order at least three is ZTF-dense. We show that if $G$ and $H$ are connected
graphs of order at least two that are both ZF-dense, then the join $G + H$ of
$G$ and $H$ is ZF-dense.
Keywords:
zero forcing sets, zero forcing number, ZF-dense
References:
- A. Aazami, Hardness Results and Approximation Algorithms for Some Problems in Graphs, Ph.D Thesis (University of Waterloo, 2008).
- A. Aazami, Domination in graphs with bounded propagation: algorithms, formulations and hardness results, J. Comb. Optim. 19 (2010) 429–456.
https://doi.org/10.1007/s10878-008-9176-7 - AIM Minimum Rank-Special Graphs Work Group, 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 - M. Alishahi, E. Rezaei-Sani and E. Sharifi, Maximum nullity and zero forcing number on graphs with maximum degree at most three, Discrete Appl. Math. 284 (2020) 179–194.
https://doi.org/10.1016/j.dam.2020.03.027 - K.F. Benson, D. Ferrero, M. Flagg, V. Furst, L. Hogben, V. Vasilevska and B. Wissman, Zero forcing and power domination for graph products, Australas. J. Combin. 70 (2018) 221–235.
- E.J. Cockayne, M.A. Henning and C.M. Mynhardt, Vertices contained in all or in no minimum total dominating set of a tree, Discrete Math. 260 (2003) 37–44.
https://doi.org/10.1016/S0012-365X(02)00447-8 - R. Davila, Bounding the Forcing Number of a Graph, Masters Thesis (Rice University, 2015).
- R. Davila, Total and Zero Forcing in Graphs, Ph.D Thesis (University of Johannesburg, 2019).
- 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, 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, 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, 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 - R. Davila and M.A. Henning, Zero forcing versus domination in cubic graphs, manuscript.
- R. Davila, M.A. Henning, C. Magnant and R. Pepper, Bounds on the connected forcing number of a graph, Graphs Combin. 34 (2018) 1159–1174.
https://doi.org/10.1007/s00373-018-1957-x - S.M. Fallat, L. Hogben, J. C.-H. Lin and B. Shader, The inverse eigenvalue problem of a graph, zero forcing, and related parameters, Notices Amer. Math. Soc. 67 (2020) 257–261.
- 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.A. 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 - M.A. Henning and M.D. Plummer, Vertices contained in all or in no minimum paired-dominating set of a tree, J. Comb. Optim. 10 (2005) 283–294.
https://doi.org/10.1007/s10878-005-4107-3 - M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013).
https://doi.org/10.1007/978-1-4614-6525-6 - 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 - C.M. Mynhardt, Vertices contained in every minimum dominating set of a tree, J. Graph Theory 31 (1999) 163–177.
https://doi.org/10.1002/(SICI)1097-0118(199907)31:3<163::AID-JGT2>3.0.CO;2-T - T. Peters, Positive semidefinite maximum nullity and zero forcing number, Electron. J. Linear Algebra 23 (2012) 815–830.
https://doi.org/10.13001/1081-3810.1559 - A. Samodivkin, Roman domination excellent graphs: trees, Commun. Comb. Optim. 3 (2018) 1–24.
- F.A. Taklimi, Zero Forcing Sets for Graphs, Ph.D Thesis (University of Regina, 2013).
Close