Maximum nullity, zero forcing number and propagation time of $\ell$-path graphs
محورهای موضوعی : Combinatorics, Graph theory
F. ‎Kheirydoost
1
,
E. Vatandoost
2
,
A. Bahraini
3
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
کلید واژه: Propagation time, zero forcing number, maximum nullity, minimum Rank,
چکیده مقاله :
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.
[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.
