1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Zero and Total Forcing Dense Graphs

Published Online: 24 Feb 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 20 Mar 2020
Accepted: 12 Dec 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 Ft(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

MSC 2010

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

[2] A. Aazami, Domination in graphs with bounded propagation: algorithms, formulations and hardness results, J. Comb. Optim. 19 (2010) 429–456. doi:10.1007/s10878-008-9176-710.1007/s10878-008-9176-7Search in Google Scholar

[3] AIM Minimum Rank-Special Graphs 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.00910.1016/j.laa.2007.10.009Search in Google Scholar

[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. doi:10.1016/j.dam.2020.03.02710.1016/j.dam.2020.03.027Search in Google Scholar

[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.Search in Google Scholar

[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. doi:10.1016/S0012-365X(02)00447-810.1016/S0012-365X(02)00447-8Search in Google Scholar

[7] R. Davila, Bounding the Forcing Number of a Graph, Masters Thesis (Rice University, 2015).Search in Google Scholar

[8] R. Davila, Total and Zero Forcing in Graphs, Ph.D Thesis (University of Johannesburg, 2019).Search in Google Scholar

[9] R. Davila and M.A. Henning, Total forcing and zero forcing in claw-free cubic graphs, Graphs Combin. 34 (2018) 1371–1384. doi:10.1007/s00373-018-1934-410.1007/s00373-018-1934-4Search in Google Scholar

[10] R. Davila and M.A. Henning, On the total forcing number of a graph, Discrete Appl. Math. 257 (2019) 115–127. doi:10.1016/j.dam.2018.09.00110.1016/j.dam.2018.09.001Search in Google Scholar

[11] R. Davila and M.A. Henning, Total forcing versus total domination in cubic graphs, Appl. Math. Comput. 354 (2019) 385–395. doi:10.1016/j.amc.2019.02.06010.1016/j.amc.2019.02.060Search in Google Scholar

[12] R. Davila and M.A. Henning, Zero forcing in claw-free cubic graphs, Bull. Malays. Math. Sci. Soc. 43 (2020) 673–688. doi:10.1007/s40840-018-00705-510.1007/s40840-018-00705-5Search in Google Scholar

[13] R. Davila and M.A. Henning, Zero forcing versus domination in cubic graphs, manuscript.Search in Google Scholar

[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. doi:10.1007/s00373-018-1957-x10.1007/s00373-018-1957-xSearch in Google Scholar

[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.10.1090/noti2033Search in Google Scholar

[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. doi:10.7151/dmgt.211710.7151/dmgt.2117Search in Google Scholar

[17] M.A. Henning and C. Löwenstein, Locating-total domination in claw-free cubic graphs, Discrete Math. 312 (2012) 3107–3116. doi:10.1016/j.disc.2012.06.02410.1016/j.disc.2012.06.024Search in Google Scholar

[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. doi:10.1007/s10878-005-4107-310.1007/s10878-005-4107-3Search in Google Scholar

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

[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. doi:10.1007/s10878-019-00475-110.1007/s10878-019-00475-1Search in Google Scholar

[21] C.M. Mynhardt, Vertices contained in every minimum dominating set of a tree, J. Graph Theory 31 (1999) 163–177. doi:10.1002/(SICI)1097-0118(199907)31:3h163::AID-JGT2i3.0.CO;2-TSearch in Google Scholar

[22] T. Peters, Positive semidefinite maximum nullity and zero forcing number, Electron. J. Linear Algebra 23 (2012) 815–830. doi:10.13001/1081-3810.155910.13001/1081-3810.1559Search in Google Scholar

[23] A. Samodivkin, Roman domination excellent graphs: trees, Commun. Comb. Optim. 3 (2018) 1–24.Search in Google Scholar

[24] F.A. Taklimi, Zero Forcing Sets for Graphs, Ph.D Thesis (University of Regina, 2013).Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo