Zero forcing, graphs on $k$ parallel paths, and linear preservers
DOI:
https://doi.org/10.13069/jacodesmath.v10i2.229Keywords:
Zero forcing number, Undirected graph, Graph on $k$ parallel paths, Linear operator, Vertex permutationAbstract
The zero forcing number of a simple loopless undirected graph, being an upper bound on the path cover number and the maximum nullity of the graph, is an important parameter in the study of the minimum rank problem. In this article, we show that the minimum $k$ for which a graph $G$ is a graph on $k$ parallel paths is an upper bound on the zero forcing number of $G$, and hence an upper bound on the path number and maximum nullity of $G$. We also determine an upper bound on the possible size (number of edges) of a graph on $k$ parallel paths. Finally we show that the only linear operators that preserve the zero forcing number of a graph are the vertex permutations.
Received: 24 October 2021 Accepted: 5 April 2022Downloads
References
AIM Minimum Rank – Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler, S. M. Cioabă, D. Cvetković, S. M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanović, H. van der Holst, K. Vander Meulen, and A. Wangsness), Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428(7) (2008) 1628–1648.
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.
F. Barioli, W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche, and H. van der Holst, Zero forcing parameters and minimum rank problems, Linear Algebra Appl. 433(2) (2010) 401–411.
L. B. Beasley and N. J. Pullman, Linear operators preserving properties of graphs, Congr. Numer. 70 (1990) 105–112.
D. D. Row, A technique for computing the zero forcing number of a graph with a cut-vertex, Linear Algebra Appl. 436(12) (2012) 4423–4432.
