The zero forcing number of Which Mycielski construction graphs are equal to their maximum nullity?

Subject Areas : Statistics

Zahra Rameh ¹ , Ebrahim Vatandoost ² , Fatemeh Ramezani ³

1 - Basic Science, Imam Khomeini International University, Qazvin, Iran.
2 - Basic Science, Imam Khomeini International University, Qazvin, Iran.
3 - Basic Science, Yazd University, Yazd, Iran.

Received: 2019-01-29 Accepted : 2021-07-18 Published : 2021-07-23

Keywords: عدد تحمیلی صفر, مینیمم رتبه, ماکسیمم پوچی, گراف مایسیلیسکی,

Abstract :

Let S denote the (initial) set of black vertices of graph G. The color-change rule converts the color of a vertex from white to black if the white vertex u is the only white neighbor of a black vertex v. The set S is said to be a zero forcing set of G if all vertices of G will be turned black after finitely many applications of the color-change rule. The zero forcing number of G is the minimum of |S| over all zero forcing sets S ⊆ V (G). In this paper, we study the zero forcing number and maximum nullity of Mycielski’s construction in some graphs. In particular, we show that the zero forcing number of some graphs with this construction equals to maximum nullity. Also we calculate the zero forcing number and maximum nullity of Mycielski graphs μ(K_n)، μ(C_n) and connected graphs of order at least 4.

References:

 

[1] عزیزی کشاورز، پریسا، تهرانیان، ابوالفضل. (1399). 'عدد احاطه­گری وقوعی گراف­ها', پژوهش­های نوین در ریاضی6(24), pp. 85-96 .

 

[2] فغانی، مرتضی. (1398). 'بررسی بیشینه تعداد رده­های احاطه­گر در رنگ­آمیزی یک گراف', پژوهش­های نوین در ریاضی .5(21), pp. 57-62

 

[3] AIM workshop Zero forcing and it’s applications, American Institute of Mathmatics, San Jose, CA, Jan.30_Feb.3, 2017 Availabele at https:// aimath.org/ past workshops/ Zeroforcing.html/.

 

[4] Alameda, J.S. Curl, E. Grez, A. Hogben, L. Schulte, A. Young, D. and Young, M. 2018. Families of graphs with maximum nullity equal to zero forcing number. Special Matrices, 6(1), pp. 56-67.

 

[5] Barioli, F. Barrett, W. Butler, S. Cioabă, S.M. Cvetković, D. Fallat, S.M. Godsil, C. Haemers, W. Hogben, L. Mikkelson, R. and Narayan, S. 2008. Zero forcing sets and the minimum rank of graphs. Linear Algebra and its Applications, 428(7), pp. 1628-1648.

 

[6] Barioli, F. Barrett, W. Fallat, S.M. Hall, H.T. Hogben, L. Shader, B. Van Den Driessche, P and Van Der Holst, H. 2010. Zero forcing parameters and minimum rank problems. Linear Algebra and its Applications, 433(2), pp. 401-411.

 

[7] Berman, A. Feidland, S. Hogben, L. Rothbium, U.G and Shader, B. 2008. An upper bound for the minimum rank of graph. Linear Algebra Appl. 429, pp. 1629-1638.

 

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

 

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

 

[10] Fallat, S.M. and Hogben, L. 2007. The minimum rank of symmetric matrices described by a graph: a survey. Linear Algebra and its Applications, 426(2-3), pp. 558-582.

 

[11] Johnson, C.R. Loewy, R. and Smith, P.A. 2009. The graphs for which the maximum multiplicity of an eigenvalue is two. Linear and Multilinear Algebra, 57(7), pp.713-736.

 

[12] Montazeri, Z. Soltankhah, N. On the Relationship Between the Zero Forcing Number and Path Cover Number for Some Graphs. 2020. Bull. Iran. Math. Soc. 46, pp. 767–776.

 

[13] Row, D.D., 2012. A technique for computing the zero forcing number of a graph with a cut-vertex. Linear Algebra and its Applications, 436(12), pp.4423-4432.

 

[14] Vatandoost, E. and Golkhandy Pour, Y. 2017. On the zero forcing number of some Cayley graphs. Algebraic Structures and Their Applications, 4(2), pp.15-25.

 

[15] Vatandoost, E. and Golkhandy Pour, Y., 2018. Maximum nullity of some Cayley graphs. Cogent Mathematics & Statistics, 5(1), pp.1462658.

 

[16] Vatandoost, E. and Nozari, K. 2018. Maximum nullity and zero forcing number of graphs with rank at most 4. Cogent Mathematics & Statistics, 5(1), pp.1437668.

 

[17] Vatandoost, E. Ramezani, F. and Alikhani, S. 2019. On the zero forcing number of generalized Sierpinski graphs. Transactions on Combinatorics, 8(1), pp. 41-50.