DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

R. Davila

Randy Davila

University of Houston-Downtown

email: davilar@uhd.edu

M.A. Henning

Michael A. Henning

University of Johannesburg

email: mahenning@uj.ac.za

0000-0001-8185-067X

R. Pepper

Ryan Pepper

University of Houston-Downtown, TX

email: pepperr@uhd.edu

Title:

Zero and total forcing dense graphs

PDF

Source:

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:

  1. A. Aazami, Hardness Results and Approximation Algorithms for Some Problems in Graphs, Ph.D Thesis (University of Waterloo, 2008).
  2. 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
  3. 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
  4. 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
  5. 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.
  6. 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
  7. R. Davila, Bounding the Forcing Number of a Graph, Masters Thesis (Rice University, 2015).
  8. R. Davila, Total and Zero Forcing in Graphs, Ph.D Thesis (University of Johannesburg, 2019).
  9. 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
  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, 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
  12. 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
  13. R. Davila and M.A. Henning, Zero forcing versus domination in cubic graphs, manuscript.
  14. 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
  15. 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.
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. A. Samodivkin, Roman domination excellent graphs: trees, Commun. Comb. Optim. 3 (2018) 1–24.
  24. F.A. Taklimi, Zero Forcing Sets for Graphs, Ph.D Thesis (University of Regina, 2013).

Close