DOI: https://doi.org/10.37236/13538
تاريخ النشر: 2026-03-13
المؤلف: Anastasia Halfpap وآخرون
الموضوع الرئيسي: الحدود والهياكل في نظرية الرسوم البيانية
نظرة عامة
يتناول هذا القسم مفهوم الحد الأدنى من الدرجة الموجبة في الرسوم البيانية غير الفارغة من النوع r، والذي يُرمز له بـ $\delta^{+}_{r-1}(H)$، والذي يُعرف بأنه أكبر عدد صحيح $k$ بحيث أن أي مجموعة فرعية $S \subset V(H)$ بحجم $r-1$ تحتوي على الأقل على حافة r واحدة من $H$ تحتوي أيضًا على الأقل على $k$ حواف r من $H$. يهدف المؤلفون إلى وضع حدود لـ $\delta^{+}_{r-1}(H)$ تضمن وجود أنواع مختلفة من الرسوم البيانية الممدودة، مع تحديد العتبات لدورات هاميلتونية من نوع Berge في الرسوم البيانية من النوع r وبشكل تقريبي لدورات هاميلتونية فضفاضة في الرسوم البيانية من النوع 3. بالإضافة إلى ذلك، يحددون الحد الأدنى من عتبة الدرجة الموجبة للتطابقات المثالية عبر جميع $r$.
في الختام، يرسم المؤلفون أوجه التشابه بين الحد الأدنى من الدرجة الموجبة والحد الأدنى من درجة الرأس في الرسوم البيانية التقليدية، مشيرين إلى أن نتائجهم تتماشى مع النتائج المعروفة في نظرية الرسوم البيانية، خاصة فيما يتعلق بنتائج من نوع ديراك وعتبات التطابق المثالي. يبرزون الإمكانية لإجراء المزيد من الأبحاث، بما في ذلك استكشاف عتبات الدرجة الموجبة لـ K-tiling، وتنقيح العتبات لدورات هاميلتونية فضفاضة، والتحقيق في استقرار الرسوم البيانية من النوع 3 فيما يتعلق بالحد الأدنى من الدرجة الموجبة. يقترح المؤلفون أنه بينما تحقق بنية 1 الحد الأدنى من الدرجة الموجبة بقيمة $n^2 – 1$، قد تكون هناك هياكل أخرى ذات خصائص مشابهة، مما يشير إلى منطقة غنية للاستكشاف المستقبلي.
مقدمة
تركز مقدمة هذه الورقة البحثية على دراسة الرسوم البيانية الفائقة الموحدة من النوع r، والتي يُرمز لها بـ $H = (V, E)$، حيث $V$ هو مجموعة الرؤوس و$E$ هو مجموعة الحواف، مع كون الحواف مجموعات فرعية من $V$ تحتوي على r عنصر. تسلط الورقة الضوء على أهمية مفاهيم الحد الأدنى من الدرجة في سياق الرسوم البيانية من النوع r، خاصة عندما يكون $r \geq 3$، حيث تظهر تفسيرات متعددة لـ “الدرجة”. يعرف المؤلفون درجة الرأس $d_1(v)$ والحد الأدنى من درجة الرأس $\delta_1(H)$، بالإضافة إلى معلمات الدرجة المشتركة، بما في ذلك الحد الأدنى من الدرجة المشتركة $\delta_{r-1}(H)$ ومعلمة جديدة، الحد الأدنى من الدرجة المشتركة الموجبة $\delta^+_{r-1}(H)$، والتي تلتقط أكبر عدد صحيح $k$ بحيث لأي مجموعة $(r-1)$ $S$، إما أن $d_{r-1}(S) = 0$ أو $d_{r-1}(S) \geq k$.
تهدف الورقة إلى استكشاف آثار الحد الأدنى من الدرجة المشتركة الموجبة على وجود الهياكل الممدودة في الرسوم البيانية من النوع r، مع رسم أوجه التشابه مع النتائج الكلاسيكية في نظرية الرسوم البيانية، مثل نظرية ديراك المتعلقة بالدورات الهاميلتونية والتطابقات المثالية. يؤكد المؤلفون أنه بينما لا يُعتبر الحد الأدنى من الدرجة المشتركة الموجبة تعميماً مباشراً للحد الأدنى من الدرجة، فإنه يقدم فهماً أكثر دقة للاستقلالية في الرسوم البيانية من النوع r، خاصة في وجود مجموعات مستقلة كبيرة. يتم تحفيز هذا الاستكشاف من خلال الأعمال السابقة ويهدف إلى وضع عتبات للدرجات للهياكل الممدودة مشابهة لتلك الموجودة في نظرية الرسوم البيانية التقليدية.
نقاش
في هذا القسم، يناقش المؤلفون مفهوم الدورات الفضفاضة الموحدة من النوع r في الرسوم البيانية الفائقة وآثارها على الدورات الهاميلتونية. يعرفون دورة فضفاضة موحدة من النوع r بطول $k$ كرسوم بيانية من النوع r تحتوي على $k(r-1)$ رأس، حيث تتشكل الحواف من تركيبات معينة من الرؤوس. يبرز المؤلفون أن وجود الدورات الهاميلتونية في الرسوم البيانية الفائقة يعتمد على بعض عتبات الدرجة والدرجة المشتركة. يقدمون نتائج رئيسية، بما في ذلك النظريتين 6 و7، اللتين تحددان الشروط التي يمكن بموجبها أن تحتوي الرسوم البيانية من النوع 3 على دورة هاميلتونية فضفاضة بناءً على درجتها المشتركة ودرجتها.
يساهم المؤلفون بشكل أكبر في الأدبيات من خلال تقديم عتبات دقيقة وتقريبية للدرجات المشتركة اللازمة لوجود دورات هاميلتونية فضفاضة والتطابقات المثالية في الرسوم البيانية من النوع r. يقدمون بنية 1، التي تعمل كمصدر رئيسي لوضع حدود دنيا على هذه العتبات. من الجدير بالذكر أنهم يظهرون أن تكوينات معينة من الرؤوس في الرسوم البيانية الفائقة يمكن أن تمنع وجود الدورات الهاميلتونية، مما يعزز الفهم للعلاقة بين درجات الرؤوس ووجود الهياكل الهاميلتونية. يختتم القسم بمناقشة آثار نتائجهم على كل من الدورات الهاميلتونية الفضفاضة والتطابقات المثالية، مع التأكيد على الفروق الدقيقة في العتبات بين هذين النوعين من الهياكل في الرسوم البيانية الفائقة.
DOI: https://doi.org/10.37236/13538
Publication Date: 2026-03-13
Author(s): Anastasia Halfpap et al.
Primary Topic: Limits and Structures in Graph Theory
Overview
The section discusses the concept of minimum positive co-degree in non-empty r-graphs, denoted as $\delta^{+}_{r-1}(H)$, which is defined as the largest integer $k$ such that any subset $S \subset V(H)$ of size $r-1$ contained in at least one r-edge of $H$ is also contained in at least $k$ r-edges of $H$. The authors aim to establish bounds for $\delta^{+}_{r-1}(H)$ that ensure the existence of various spanning subgraphs, specifically identifying the thresholds for Berge Hamiltonian cycles in r-graphs and asymptotically for loose Hamiltonian cycles in 3-graphs. Additionally, they determine the minimum positive co-degree threshold for perfect matchings across all $r$.
In conclusion, the authors draw parallels between minimum positive co-degree and minimum vertex degree in traditional graphs, noting that their findings align with established results in graph theory, particularly regarding Dirac-type results and perfect matching thresholds. They highlight the potential for further research, including exploring positive co-degree thresholds for K-tiling, refining the thresholds for loose Hamiltonian cycles, and investigating the stability of 3-graphs with respect to their minimum positive co-degree. The authors suggest that while their Construction 1 achieves a minimum positive co-degree of $n^2 – 1$, there may be other structures with similar properties, indicating a rich area for future exploration.
Introduction
The introduction of this research paper focuses on the study of r-uniform hypergraphs, denoted as $H = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges, with edges being r-element subsets of $V$. The paper highlights the significance of minimum degree concepts in the context of r-graphs, particularly when $r \geq 3$, where multiple interpretations of “degree” arise. The authors define vertex degree $d_1(v)$ and minimum vertex degree $\delta_1(H)$, as well as co-degree parameters, including minimum co-degree $\delta_{r-1}(H)$ and a new parameter, minimum positive co-degree $\delta^+_{r-1}(H)$, which captures the largest integer $k$ such that for any $(r-1)$-set $S$, either $d_{r-1}(S) = 0$ or $d_{r-1}(S) \geq k$.
The paper aims to explore the implications of minimum positive co-degree on the existence of spanning structures in r-graphs, drawing parallels to classical results in graph theory, such as Dirac’s theorem regarding Hamiltonian cycles and perfect matchings. The authors emphasize that while minimum positive co-degree is not a direct generalization of minimum degree, it offers a more nuanced understanding of independence in r-graphs, particularly in the presence of large independent sets. This exploration is motivated by previous works and aims to establish degree thresholds for spanning structures analogous to those in traditional graph theory.
Discussion
In this section, the authors discuss the concept of r-uniform loose cycles in hypergraphs and their implications for Hamiltonian cycles. They define an r-uniform loose cycle of length $k$ as an r-graph with $k(r-1)$ vertices, where edges are formed by specific vertex combinations. The authors highlight that the existence of Hamiltonian cycles in hypergraphs depends on certain degree and co-degree thresholds. They present key results, including Theorems 6 and 7, which establish conditions under which a 3-graph can contain a loose Hamiltonian cycle based on its co-degree and degree.
The authors further contribute to the literature by providing exact and asymptotic thresholds for co-degrees necessary for the existence of loose Hamiltonian cycles and perfect matchings in r-graphs. They introduce Construction 1, which serves as a primary source for establishing lower bounds on these thresholds. Notably, they demonstrate that certain configurations of vertices in hypergraphs can prevent the existence of Hamiltonian cycles, thereby refining the understanding of the relationship between vertex degrees and the presence of Hamiltonian structures. The section concludes with a discussion of the implications of their findings for both loose Hamiltonian cycles and perfect matchings, emphasizing the nuanced differences in thresholds for these two types of structures in hypergraphs.