Maximum nullity‎, ‎zero forcing number and propagation time of $\ell$-path graphs

Subject Areas : Combinatorics, Graph theory

F. ‎Kheirydoost ¹ , E. Vatandoost ² , A. Bahraini ³

1 - Department of Mathematics, Imam Khomeini International University, P.O. Box 34149-16818, Qazvin, Iran
2 - Department of Mathematics, Imam Khomeini International University, P.O. Box 34149-16818, Qazvin, Iran
3 - Department of Mathematics, Islamic Azad University, Central Tehran Branch, Tehran, Iran

Received: 2023-08-22 Accepted : 2023-11-23 Published : 2023-10-01

Keywords: Propagation time, zero forcing number, maximum nullity, minimum Rank,

Abstract :

‎Let $G$ be a graph with each vertex is colored either white or black‎. ‎A white vertex is changed to a black vertex when it is the only white neighbor of a black vertex (color-change rule)‎. ‎A zero forcing set $S$ of a graph $G$ is a subset of vertices $G$ with black vertices‎, ‎all other vertices $G$ are white‎, ‎such that after finitely many applications of the color-change rule all of vertices $G$ becomes black‎. ‎The zero forcing number of $G$ is the minimum cardinality of a zero forcing set in $G$‎, ‎denoted by $Z(G).$ In this paper‎, ‎we define $\ell-$Path graphs‎. ‎We give some $\ell-$Path and $\ell-$Ciclo graphs such that their maximum nullity are equal to their zero forcing number‎. ‎Also‎, ‎we obtain minimum propagation time and maximum propagation time for them‎.

References:

[1] AIM Minimum Rank, Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), 1628-1648.

[2] E. Almodovar, L. DeLoss, L. Hogben, K. Hogenson, K. Murphy, T. Peters, C. A. Ram` ırez, Minimum rank, maximum nullity and zero forcing number for selected graph families, Math. Sci. Publ. 3 (4) (2010), 371-392.

[3] A. R. Ashrafi, A. Hamzeh, S. Hossein Zadeh, Calculation of some topological indices of splices and links of graphs, J. Appl. Math. Inform. 29 (1-2) (2011), 327-335.

[4] F. Barioli, S. Fallat, D. Hershkowitz, H. T. Hall, L. Hogben, H. Van der Holst, B. Shader, On the minimum rank of not necessarily symmetric matrices: a preliminary study, Electron. J. Linear Algebra. 18 (2009), 126-145.

[5] A. Berman, S. Friedland, L. Hogben, U. G. Rothblum, B. Shader, An upper bound for the minimum rank of a graph, Linear Algebra Appl. 429 (7) (2008), 1629-1638.

[6] D. Burgarth, S. Bose, C. Bruder, V. Giovannetti, Local controllability of quantum netvorks, Phys. Rev. A. 79 (2009), 79:060305.

[7] D. Burgarth, V. Giovannetti, Full control by locally induced relaxation, Phys. Rev. Lett. 99 (2007), 99:100501.

[8] S. Butler, M. Young, Throttling zero forcing propagation speed on graphs, Australas. J. Combin. 57 (2013), 65-71.

[9] K. B. Chilakamarri, N. Dean, C. X. Kang, E. Yi, Iteration index of a zero forcing set in a graph, Bull. Inst. Combin. Appl. 64 (2012), 57-72.

[10] R. Davila, T. Kalinowski, S. Stephen, A lower bound on the zero forcing number, Discrete Appl. Math. 250 (2018), 363-367.

[11] R. Davila, F. Kenter, Bounds for the zero forcing number of graphs with large girth, Theo. Appl. Graphs. 2 (2015), 2:1.

[12] C. J. Edholm, L. Hogben, M. Huynh, J. LaGrange, D. D. Row, Vertex and edge spread of zero forcing number, maximum nullity and minimum rank of a graph, Linear Algebra Appl. 436 (12) (2012), 4352-4372.

[13] L. Eroh, C. X. Kang, E. Yi, A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs, Acta. Math. Sinica. 33 (6) (2017), 731-747.

[14] S. Fallat, L. Hogben, The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebra Appl. 426 (2007), 558-582.

[15] L. Hogben, M. Huynh, N. Kingsley, S. Meyer, S. Walker, M. Young, Propagation time for zero forcing on a graph, Discrete Appl. Math. 160 (13) (2012), 1994-2005.

[16] T. Kalinowski, N. Kamcev, B. Sudakov, The zero forcing number of graphs, Siam J. Discrete. Math. 33 (1) (2019), 95-115.

[17] M. Khosravi, S. Rashidi and A. Sheikhhosseni, Connected zero forcing sets and connected propagation time of graphs, Trans. Combin. 9 (2) (2020), 77-88.

[18] Z. Rameh, E. Vatandoost, Some Cayley Graphs With Propagation Time 1, J. Iranian Math. Soc. 2 (2) (2021), 111-122.

[19] E. Vatandoost, Y. Golkhandy Pour, On the zero forcing number of some Cayley graphs, Algebraic Struct. Appl. 4 (2) (2017), 15-25.