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

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

زهرا براتی ^{1 *} , مژگان افخمی ² , کاظم خشیارمنش ³

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.