Article in volume
Authors:
Title:
Spectral bounds for the zero forcing number of a graph
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 971-982
Received: 2022-07-05 , Revised: 2022-11-27 , Accepted: 2022-11-27 , Available online: 2023-01-28 , https://doi.org/10.7151/dmgt.2482
Abstract:
Let $Z(G)$ be the zero forcing number of a simple connected graph $G$.
In this paper, we study the relationship between the zero forcing number of
a graph and its (normalized) Laplacian eigenvalues. We provide the upper and
lower bounds on $Z(G)$ in terms of its (normalized) Laplacian eigenvalues,
respectively. Our bounds extend the existing bounds for regular graphs.
Keywords:
zero forcing number, eigenvalue, bound
References:
- 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 - F. Barioli, W. Barrett, S. Butler and et al., 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 - J. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London, 1976).
- A.E. Brouwer and W.H. Haemers, Spectra of Graphs (Springer, New York, 2012).
https://doi.org/10.1007/978-1-4614-1939-6 - D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Phys. Rev. Lett. 99(10) (2007) 100501.
https://doi.org/10.1103/PhysRevLett.99.100501 - S. Butler, Eigenvalues and Structures of Graphs, PhD Thesis (University of California, San Diego, 2008).
- Y. Caro and R. Pepper, Dynamic approach to $k$-forcing, Theory Appl. Graphs 2 (2) (2015) Article 2.
https://doi.org/10.20429/tag.2015.020202 - F.R.K. Chung, Spectral Graph Theory (CBMS Reg. Conf. Ser. Math., 92 Providence, RI: AMS, 1997).
https://doi.org/10.1090/cbms/092 - R. Davila and M.A. Henning, Zero forcing versus domination in cubic graphs, J. Comb. Optim. 41 (2021) 553–577.
https://doi.org/10.1007/s10878-020-00692-z - 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 - T. Kalinowski, N. Kam\u{c}ev and B. Sudakov, The zero forcing number of graphs, SIAM J. Discrete Math. 33 (2019) 95–115.
https://doi.org/10.1137/17M1133051 - F.A. Taklimi, Zero Forcing Sets for Graphs, PhD Thesis (University of Regina, Regina, Canada, 2013).
- W.Q. Zhang, J.F. Wang, W.F. Wang and S. Ji, On the zero forcing number and spectral radius of graphs, Electron. J. Combin. 29 (1) (2022) #P1.33.
https://doi.org/10.37236/10638
Close