مطالعه‌ی خمیدگی گراف های حاصل از چند عمل گرافی

الموضوعات :

زهرا براتی ¹ , مژگان افخمی ² , کاظم خشیارمنش ³

1 - گروه رياضي، دانشکده علوم پايه، دانشگاه کوثر بجنورد، بجنورد، ايران
2 - گروه رياضي، دانشگاه نیشابور، نیشابور، ايران
3 - گروه رياضي، دانشگاه فردوسی مشهد، مشهد، ايران

تاريخ الإرسال : 04 الجمعة , جمادى الثانية, 1443 تاريخ التأكيد : 06 السبت , رجب, 1444 تاريخ الإصدار : 22 الأربعاء , ربيع الأول, 1446

الکلمات المفتاحية: Vertex corona product, Join of two graphs, skewness, Edge corona product, 𝜋-skew,

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

گراف G=(V,E)، را مسطح می‌گوییم هرگاه بتوان آن را بر روی صفحه چنان ترسیم کرد که یال‌های آن فقط در رئوس‌شان اشتراک داشته باشند. همچنین خمیدگی گراف G، که آن را با نماد sk(G) نمایش می‌دهیم، برابر است با کمترین تعداد یالی که با حذف آنها از گراف G، گراف حاصل یک گراف مسطح شود. در نظریه گراف، از این عدد به عنوان معیاری برای سنجش دوری یا نزدیکی یک گراف از مسطح بودن استفاده می‌شود. در این مقاله، خمیدگی الحاق گراف‌ها با مسیرها و دورها مورد مطالعه قرار گرفته است. در روند مطالعاتی‌مان، ابتدا، خمیدگی گراف های بادبزن تعمیم یافته و گراف چرخ n- فولد را به طور کامل محاسبه کرده‌ایم. سپس چند قضیه در مورد الحاق گراف‌ها با مسیرها اثبات کرده‌ایم که با استفاده از آن‌ها خمیدگی الحاق گراف‌های کامل، گراف‌های ستاره و گراف‌های دو بخشی کامل با مسیرها، به طور کامل محاسبه شده‌اند. همچنین در مورد محاسبه‌ی خمیدگی کرونای رأسی و یالی دو گراف نیز فرمول‌های مفیدی ارائه شده است.

المصادر:

[1] A. Liebers, Planarizing graphs–a survey and annotated bibliography, Journal of Graph Algorithms and Applications, 5: 1-17 (2001).

[2] P. C. Liu, R. C. Geldmacher, On the deletion of nonplanar edges of a graph, Congressus Numerantium, 24: 727–738 (1979).

[3] M. Yannakakis, Edge-deletion problems, SIAM Journal on Computing, 10: 297–309 (1981).

[4] G. L. Chia, K. A. Sim, On the skewness of the join of graphs, Discrete Applied Mathematics, 161: 2405–2408 (2013).

[5] G.L. Chia, C.L. Lee, Crossing numbers and skewness of some generalized Petersen graphs, in: Lecture Notes in Computer Science, Vol. 3330, Springer-Verlag, 80–86 (2005).

[6] G.L. Chia, C.L. Lee, Skewness of some generalized Petersen graphs and related graphs, Frontiers of Mathematics in China, 7: 427–436 (2012).

[7] G.L. Chia, C.L. Lee, Skewness and crossing numbers of graphs, Bulletin of the Institute of Combinatorics and its Applications, 55: 17–32 (2009).

[8] R.J. Cimikowski, Graph planarization and skewness, Congressus Numerantium, 88: 21–32 (1992).

[9] Z.D. Ouyang, F.M. Dong, R.X. Zhang, E.G. Tay, Properties of -skew Graphs with Applications, Acta Mathematica Sinica, English Series, 37: 641–656 (2021).