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

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

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

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

تاریخ دریافت : 1400/10/17 تاریخ پذیرش : 1401/11/08 تاریخ انتشار : 1403/07/04

کلید واژه: Vertex corona product, Join of two graphs, skewness, Edge corona product, 𝜋-skew,

چکیده مقاله :

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

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

We say a graph G=(V,E) is planar when we can draw it on the plane in such a way that its edges only intersect with each other at their ends. Also, the skewness of a graph G, denoted by sk(G), is equal to the minimum number of edges that by deleting them from G, the resulted graph is planar. In graph theory, this number is used as a parameter that measures how close a graph is to planarity. In this paper, the skewness of the join of graphs with paths and cycles is studied. At first, we calculate the skewness of the generalized fans and the n-fold wheels. Then, we prove some results concerning the skewness for the join of graphs with paths and use these results to determine completely the skewness of the join of complete graphs, star graphs and complete bipartite graphs with paths. At the end, some useful formulas are presented for calculating the skewness of vertex corona product and edge corona product of two graphs.

منابع و مأخذ:

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