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

الموضوعات :

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

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

تاريخ الإرسال : 23 الثلاثاء , جمادى الأولى, 1440 تاريخ التأكيد : 08 الأحد , ذو الحجة, 1442 تاريخ الإصدار : 13 الجمعة , ذو الحجة, 1442

الکلمات المفتاحية: Zero forcing number, maximum nullity, minimum rank, Mycielski graph,

ملخص المقالة :

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