عدد تحمیلی صفر چه گرافهایی با ساختار مایسیلیسکی با ماکسیمم پوچی آنها برابر است؟

محورهای موضوعی : آمار

زهرا رامه ¹ , ابراهیم وطن دوست ² , فاطمه رمضانی ³

1 - دانشکده علوم پایه، دانشگاه بین المللی امام خمینی(ره)، قزوین، ایران.
2 - دانشکده علوم پایه، دانشگاه بین المللی امام خمینی(ره)، قزوین، ایران.
3 - دانشکده علوم پایه، دانشگاه یزد، یزد، ایران.

تاریخ دریافت : 1397/11/09 تاریخ پذیرش : 1400/04/27 تاریخ انتشار : 1400/05/01

کلید واژه: Zero forcing number, maximum nullity, minimum rank, Mycielski graph,

چکیده مقاله :

فرض کنید S نشان دهنده مجموعه رئوس با رنگ سیاه (اولیه) گراف G باشد. قانون تغییر رنگ، رنگ یک رأس سفید را به سیاه تبدیل می کند اگر رأس سفید u تنها همسایه سفید رأس سیاه v باشد. مجموعه S یک مجموعه تحمیلی صفر G است هرگاه بعد از تعداد متناهی اعمال قانون تغییر رنگ، رنگ تمامی رئوس به سیاه تغییر کنند. تعداد اعضای یک مجموعه‌ی تحمیلی صفر با کمترین عضو را عدد تحمیلی صفر گراف می نامند.در این مقاله عدد تحمیلی صفر و ماکسیمم پوچی برخی گراف‌ها با ساختار مایسیلیسکی را بررسی می‌کنیم. به ویژه به ازای برخی گراف‌ها با این ساختار نشان می‌دهیم عدد تحمیلی صفر گراف با ماکسیمم پوچی آن برابر است. همچنین عدد تحمیلی صفر و ماکسیمم پوچی گراف‌ها‌ی مایسیلیسکی μ(K_n)، μ(C_n)و گراف‌های همبند با حداقل 4 رأس را محاسبه کرده‌ایم.

چکیده انگلیسی:

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.

منابع و مأخذ:

 

[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.