گراف‌های صحیح تطابقی از مرتبه کم

الموضوعات :

سمیه خلاشی قزل احمد ¹ (عضو هیات علمی/گروه ریاضی، دانشکده علوم پایه، واحد علوم و تحقیقات،‌دانشگاه آزاد اسلامی، تهران ایران)

تاريخ الإرسال : 03 الإثنين , شعبان, 1440 تاريخ التأكيد : 27 الأربعاء , جمادى الأولى, 1441 تاريخ الإصدار : 05 الخميس , ربيع الأول, 1442

الکلمات المفتاحية: Matching polynomial, Matching integral graph, Matching,

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

در این مقاله به بررسی گرافهای صحیح تطابقی از مرتبه کم می‌پردازیم. یک گراف را صحیح تطابقی گوییم هر گاه تمام ریشه‌‌های چندجمله‌ایی تطابقی آن صحیح باشند. گراف‌های صحیح تطابقی برای اولین بار توسط اکبری و همکاران مورد مطالعه قرار گرفتند. آن‌ها تمام گراف‌های قابل ردیابی و تمام گراف‌های منظم که صحیح تطابقی هستند را شناسایی نمودند. همچنین نشان دادند هیچ گراف فاقد پنجه‌ایی وجود ندارد که صحیح تطابقی باشد. به‌علاوه ثابت کردند گراف کامل از مرتبه دو تنها گرافی است که تطابق کامل دارد و صحیح تطابقی است. در این مقاله تمام گراف‌های همبند صحیح تطابقی از مرتبه حداکثر هفت را شناسایی می‌کنیم و نشان می‌دهیم دقیقا هشت گراف صحیح تطابقی از مرتبه حداکثر هفت وجود دارد. به‌علاوه نشان می‌کنیم یک گراف همبند صحیح تطابقی از مرتبه هشت حتما دارای تطابق سه یالی بوده و سایز آن برابر چهارده است. در نهایت تمام گراف‌های همبند صحیح تطابقی با ماکزیم درجه رئوس حداکثر سه را شناسایی می‌کنیم.

المصادر:

[1] C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, Inc., 1993.

 

[2] C.D. Godsil, Algebraic matching theory, Electron. J. Combin., 2 (1995), 1-14.

 

[3] C.D. Godsil and I. Gutman, On the theory of the matching polynomial, J. Graph Theory, 5(2) (1981), 137-144.

 

[4] I. Gutman, The matching polynomial, MATCH Commun. Math. Comput. Chem., 6 (1979), 75-91.

 

[5] I. Gutman and F. Harary, Generalizations of the matching polynomial, Utilitas Math., 24 (1983), 97-106.

 

[12] C.Y. Ku and W. Chen, An analogue of the Gallai-Edmond structure theorem for non-zero roots of the matching polynomial, J. Combin. Theory Ser. B, 100 (2010), 119-127.

 

[13] S. Khalashi Ghezelahmad, On matching integral graphs, Mathematical Sciences, 13 (2019), 387–394.

 

[6] I. Gutman and S. Wagnerb, The matching energy of a graph, Discrete Appl. Math., 160 (2012), 2177-2187.

 

[7] F. Harary and A.J. Schwenk, Which graphs have integral spectra? Graphs and Combinatorics., Lecture Notes in Math., Springer-Verlag, Berlin, 406 (1974), 45-51.

 

[8] K.T. Bali ska, D. Cvetkovi , Z. Radosavljevi , S.K. Simi  and D. Stevanovi , A survey on integral graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., 13 (2002), 42-65.

 

[9] S. Akbari, P. Csikvári, A. Ghafari, S. Khalashi Ghezelahmad and M. Nahvi, Graphs with integer matching polynomial zeros, Discrete Appl. Math., 224 (2017), 1-8.

 

[10] O.J. Heilmann and E.H. Lieb, Theory of monomer-dimer systems, Commun. Math. Physics, 25 (1972), 190-232.

 

[11] E. Ghorbani, Graphs with few matching roots, Graphs Combin. 29 (2013), 1377-1381.