جميع الرسوم البيانية لنوافذ الورد العامة هي هاملتونية
All generalized rose window graphs are hamiltonian

شارك:
المجلة: Graphs and Combinatorics، المجلد: 42، العدد: 2
DOI: https://doi.org/10.1007/s00373-026-03016-w
تاريخ النشر: 2026-02-23
المؤلف: Simona Bonvicini وآخرون
الموضوع الرئيسي: أبحاث نظرية المجموعات المحدودة

نظرة عامة

في هذا القسم، يناقش المؤلفون البيكيركولات، والتي تُعرف بأنها رسوم بيانية منتظمة، ذات درجة \( d \) وتتميز بتحويل آلي شبه منتظم من الرتبة \( m \) الذي ينشئ مداري قمة بحجم \( m \). كل مدار قمة يتوافق مع رسم بياني دائري من الرتبة \( m \)، بينما تشكل الحواف المتبقية رسمًا بيانيًا ثنائي القطب منتظمًا من الدرجة \( s \) (حيث \( 1 \leq s \leq d \)) الذي يربط بين المدارين. مجموعة ملحوظة من البيكيركولات هي الرسوم البيانية بيترسن المعممة، التي تتميز بـ \( d = 3 \) و \( s = 1 \).

يشير المؤلفون إلى نتيجة مهمة لبراين ألباتش من عام 1983، التي أثبتت أن جميع الرسوم البيانية بيترسن المعممة هي هاملتونية، باستثناء عائلة \( G(m, 2) \) حيث \( m \equiv 5 \mod 6 \). يتكهنون بأن هذا الاستثناء فريد بين جميع البيكيركولات المتصلة ذات الدرجة لا تقل عن 2. تشير الأدلة الداعمة إلى أن التكهن صحيح بالنسبة للبيكيركولات المكعبة، ويقدم المؤلفون برهانًا للبيكيركولات الرباعية مع \( s = 2 \)، والتي تُعرف أيضًا باسم الرسوم البيانية لنافذة الورد المعممة، مما يساهم في فهم الخصائص الهاملتونية في هذه الفئة من الرسوم البيانية.

مقدمة

في هذا القسم، يبني المؤلفون على العمل الأساسي لبراين ألباتش بشأن الرسوم البيانية بيترسن المعممة وخصائص الهاملتونية للرسوم البيانية المكعبة للتحقيق في وجود دورات هاملتونية في فئة أوسع من الرسوم البيانية البيكيركولات. تُعرف الرسوم البيانية البيكيركولات بأنها رسوم بيانية منتظمة، ذات درجة \( d \) تمتلك تحويلًا آليًا شبه منتظم من الرتبة \( m \)، والذي ينشئ مداري قمة بحجم \( m \). يشير المؤلفون إلى أنه بينما يُعرف أن جميع الرسوم البيانية الدائرية هي هاملتونية، فإن حالة الهاملتونية للبيكيركولات لا تزال غير محسومة إلى حد كبير، خاصة بالنسبة لرسوم كايلي على المجموعات الثنائية، والتي هي مجموعة فرعية من البيكيركولات.

يقترح المؤلفون التكهن 1.1، مشيرين إلى أن كل بيكيركولات متصلة، باستثناء الرسم البياني الكامل $K_2$ وبعض الرسوم البيانية بيترسن المعممة $G(m, 2)$ حيث $m \equiv 5 \mod 6$، هي هاملتونية. يبرزون أن تصنيف الرسوم البيانية بيترسن المعممة الهاملتونية قد تم توسيعه ليشمل الرسوم البيانية I، والتي هي نوع محدد من البيكيركولات مع المعلمات $d = 3$ و $s = 1$، وقد تم إثبات أن جميع الرسوم البيانية I الصحيحة هي هاملتونية. تهدف الورقة إلى تعزيز فهم البيكيركولات المكعبة، مع التركيز بشكل خاص على الحالة التي يكون فيها $d = 4$ و $s = 2$، والتي تُعرف باسم الرسوم البيانية لنافذة الورد المعممة، وتقدم نتائجها الرئيسية في هذا السياق.

نقاش

في هذا القسم، يثبت المؤلفون أن كل رسم بياني لنافذة الورد المعممة المتصلة هو هاملتوني، كما هو مذكور في النظرية 1.2. تم تقديم الرسوم البيانية لنافذة الورد المعممة، التي قدمها ستيف ويلسون في عام 2008، من الرسوم البيانية بيترسن المعممة عن طريق إضافة أشعة مع الحفاظ على التناظر شبه المنتظم. تتمتع هذه الرسوم البيانية بخصائص تناظر غنية، كونها جزءًا من فئة البيكيركولات، حيث أن بعضها متساوي القمة والبعض الآخر متساوي الحافة أو رسوم كايلي. يرسم المؤلفون أوجه التشابه بين الرسوم البيانية لنافذة الورد المعممة والرسوم البيانية I، مشيرين إلى أنه بينما تكون الأولى متصلة دائمًا، قد لا تكون الأخيرة كذلك. يؤدي إزالة تطابق من الأشعة من رسم بياني لنافذة الورد المعممة المتصلة إلى رسم بياني غير متصل يتكون من الرسوم البيانية I، ما لم يتم استيفاء شروط حسابية معينة.

لإثبات الهاملتونية للرسوم البيانية لنافذة الورد المعممة، طور المؤلفون أدوات جديدة قد تساعد في بناء دورات هاملتونية في عائلات البيكيركولات الأوسع. كما يربطون نتائجهم بالتكهن لوفاز، مؤكدين أن كل رسم بياني متصل محدود متساوي القمة، باستثناء خمسة استثناءات، هو هاملتوني. توضح الورقة هيكلها، مع تقديم الأقسام اللاحقة لتعريفات رسمية للبيكيركولات، والرسوم البيانية لنافذة الورد المعممة، والرسوم البيانية I، إلى جانب مراجعة لنتائج الهاملتونية. يصنف المؤلفون دورات هاملتونية في الرسوم البيانية I إلى ثلاثة أنواع، والتي تُستخدم بعد ذلك في بناء دورات هاملتونية في الرسوم البيانية لنافذة الورد المعممة. يتضمن البرهان إزالة تطابق مناسب من رسم بياني لنافذة الورد المعممة للحصول على رسم بياني I، حيث يحتوي كل مكون متصل على دورة هاملتونية أو مسار يمكن دمجه لتشكيل دورة هاملتونية في الرسم البياني الأصلي. تمتد تداعيات هذه النتائج إلى الرسوم البيانية البيكيركولات الأكثر عمومية، مما يحدد الشروط التي تكون فيها هاملتونية.

Journal: Graphs and Combinatorics, Volume: 42, Issue: 2
DOI: https://doi.org/10.1007/s00373-026-03016-w
Publication Date: 2026-02-23
Author(s): Simona Bonvicini et al.
Primary Topic: Finite Group Theory Research

Overview

In this section, the authors discuss bicirculants, which are defined as regular, d-valent graphs featuring a semiregular automorphism of order \( m \) that creates two vertex-orbits of size \( m \). Each vertex orbit corresponds to a circulant graph of order \( m \), while the remaining edges form a regular bipartite graph of valence \( s \) (where \( 1 \leq s \leq d \)) that connects the two orbits. A notable subset of bicirculants is the generalized Petersen graphs, characterized by \( d = 3 \) and \( s = 1 \).

The authors reference a significant result by Brian Alspach from 1983, which established that all generalized Petersen graphs are Hamiltonian, with the exception of the family \( G(m, 2) \) for \( m \equiv 5 \mod 6 \). They conjecture that this exception is unique among all connected bicirculants with valence at least 2. Supporting evidence suggests the conjecture holds for cubic bicirculants, and the authors provide a proof for quartic bicirculants with \( s = 2 \), also referred to as generalized rose window graphs, thereby contributing to the understanding of Hamiltonian properties in this class of graphs.

Introduction

In this section, the authors build upon the foundational work of Brian Alspach regarding generalized Petersen graphs and the Hamiltonian properties of cubic graphs to investigate the existence of Hamilton cycles in a broader category of bicirculant graphs. A bicirculant graph is defined as a regular, d-valent graph that possesses a semiregular automorphism of order m, which creates two vertex-orbits of size m. The authors note that while all circulant graphs are known to be Hamiltonian, the Hamiltonian status of bicirculants remains largely unresolved, particularly for Cayley graphs on dihedral groups, which are a subset of bicirculants.

The authors propose Conjecture 1.1, suggesting that every connected bicirculant, with the exception of the complete graph $K_2$ and specific generalized Petersen graphs $G(m, 2)$ where $m \equiv 5 \mod 6$, is Hamiltonian. They highlight that the classification of Hamiltonian generalized Petersen graphs has been extended to I-graphs, which are a specific type of bicirculant with parameters $d = 3$ and $s = 1$, and it has been established that all proper I-graphs are Hamiltonian. The paper aims to advance the understanding of cubic bicirculants, particularly focusing on the case where $d = 4$ and $s = 2$, referred to as generalized rose window graphs, and presents their main results in this context.

Discussion

In this section, the authors establish that every connected generalized rose window graph is Hamiltonian, as stated in Theorem 1.2. Generalized rose window graphs, introduced by Steve Wilson in 2008, are derived from generalized Petersen graphs by adding spokes while maintaining semiregular symmetry. These graphs exhibit rich symmetry properties, being part of the bicirculant class, with some being vertex-transitive and others edge-transitive or Cayley graphs. The authors draw parallels between generalized rose window graphs and I-graphs, noting that while the former are always connected, the latter may not be. The removal of a matching of spokes from a connected generalized rose window graph leads to a disconnected graph composed of I-graphs, unless specific arithmetic conditions are met.

To demonstrate the Hamiltonicity of generalized rose window graphs, the authors developed novel tools that may aid in constructing Hamilton cycles in broader bicirculant families. They also connect their findings to the Lovász conjecture, confirming that every finite connected vertex-transitive graph, barring five exceptions, is Hamiltonian. The paper outlines its structure, with subsequent sections providing formal definitions of bicirculants, generalized rose window graphs, and I-graphs, alongside a review of Hamiltonicity results. The authors classify Hamilton cycles in I-graphs into three types, which are then utilized in constructing Hamilton cycles in generalized rose window graphs. The proof involves removing a suitable matching from a generalized rose window graph to obtain an I-graph, where each connected component contains a Hamilton cycle or path that can be combined to form a Hamilton cycle in the original graph. The implications of these results extend to more general bicirculant graphs, establishing conditions under which they are Hamiltonian.