DOI: https://doi.org/10.1016/j.dam.2026.02.055
تاريخ النشر: 2026-03-13
المؤلف: Zhenyun Du وآخرون
الموضوع الرئيسي: نظرية الرسوم البيانية وتطبيقاتها
نظرة عامة
في هذا القسم، يعرف المؤلفون عاملًا زوجيًا للرسم البياني \( G \) كفرع ممتد \( F \) حيث يكون الدرجة \( d_F(v) = 2k \) لكل رأس \( v \in V(G) \)، مع \( k \in \mathbb{N}^+ \). يقدم البحث شرطًا كافيًا لوجود مثل هذا العامل الزوجي في الرسوم البيانية المتصلة ذات الترتيب الزوجي التي لها درجة دنيا \( \delta \). يتم اشتقاق هذا الشرط من خصائص نصف القطر الطيفي لمصفوفة لابلاس بدون إشارة، مما يدل على علاقة بين نظرية الرسوم البيانية الطيفية والخصائص الهيكلية للعوامل الزوجية في الرسوم البيانية.
مقدمة
تناقش مقدمة هذه الورقة البحثية المفاهيم الأساسية في نظرية الرسوم البيانية، مع التركيز بشكل خاص على الخصائص والعوامل للرسوم البيانية غير الموجهة، المحدودة، والبسيطة. تعرف المصطلحات الرئيسية مثل ترتيب وحجم الرسم البياني، درجة الرأس، ومفهوم العوامل الزوجية، بما في ذلك الحالة المحددة للعوامل 2. يسلط القسم الضوء على المساهمات المهمة في هذا المجال، بما في ذلك نظرية العامل 1 لتوت، والعديد من الشروط التي وضعها باحثون مثل أوتا وتوكودا، ورايجيك وآخرون، وزو وآخرون لوجود العوامل 2 والعوامل الزوجية في فئات مختلفة من الرسوم البيانية.
علاوة على ذلك، تتناول المقدمة نظرية الرسوم البيانية الطيفية، معرفًا مصفوفة الجوار ومصفوفة لابلاس بدون إشارة، جنبًا إلى جنب مع أطوالها الطيفية. تشير إلى الأعمال السابقة التي تربط شروط نصف القطر الطيفي بوجود المطابقات المثالية والعوامل الزوجية في الرسوم البيانية. تهدف الورقة إلى وضع شرط كافٍ جديد يتعلق بنصف القطر الطيفي لمصفوفة لابلاس بدون إشارة للرسوم البيانية المتصلة ذات الترتيب الزوجي، مما يؤدي إلى النظرية 1.1، التي تقدم معيارًا محددًا لوجود عامل زوجي في مثل هذه الرسوم البيانية تحت شروط معينة.
نقاش
في قسم النقاش، يقدم المؤلفون عدة ليمات تمهيدية تعتبر حاسمة لإثبات النظرية الرئيسية المتعلقة بوجود عوامل زوجية في الرسوم البيانية. بشكل ملحوظ، تؤسس الليمات 2.2 شرطًا كافيًا لوجود عوامل زوجية من خلال ربط نسبة بعض هياكل الرسوم البيانية، بينما تؤكد الليمات 2.3 أن نسبة الرسم البياني لا تقل عن تلك الخاصة بفروعه، مع المساواة فقط عندما تكون الرسوم البيانية متطابقة. يقدم القسم أيضًا مفهوم التقسيمات العادلة للمصفوفات، حيث تحتفظ مصفوفة النسبة المقابلة بالخصائص الطيفية للمصفوفة الأصلية، كما هو موضح في الليمات 2.4 و2.5.
ثم يتم تفصيل إثبات النظرية 1.1، موضحًا العلاقة بين نصف القطر الطيفي لمصفوفة لابلاس بدون إشارة ووجود عوامل زوجية. يستخدم المؤلفون نهج التناقض، مفترضين أن الرسم البياني \( G \) يفتقر إلى عامل زوجي واستنتاج عدم المساواة التي تتضمن نسبة \( G \) والرسوم البيانية المُنشأة \( G_1 \)، \( G_2 \)، و \( G_3 \). يتم تقسيم التحليل إلى ثلاث حالات بناءً على حجم مجموعة فرعية معينة \( S \) من الرؤوس، مما يؤدي إلى عدم المساواة المختلفة التي تتعارض في النهاية مع الافتراض الأولي. تسلط النتائج الضوء على العلاقات المعقدة بين هياكل الرسوم البيانية وخصائصها الطيفية، مما يعزز أهمية التقسيمات العادلة في فهم عوامل الرسوم البيانية.
DOI: https://doi.org/10.1016/j.dam.2026.02.055
Publication Date: 2026-03-13
Author(s): Zhenyun Du et al.
Primary Topic: Graph theory and applications
Overview
In this section, the authors define an even factor of a graph \( G \) as a spanning subgraph \( F \) where the degree \( d_F(v) = 2k \) for every vertex \( v \in V(G) \), with \( k \in \mathbb{N}^+ \). The paper presents a sufficient condition for the existence of such an even factor in connected graphs of even order that have a minimum degree \( \delta \). This condition is derived from the properties of the signless Laplacian spectral radius, indicating a relationship between spectral graph theory and the structural characteristics of even factors in graphs.
Introduction
The introduction of this research paper discusses fundamental concepts in graph theory, particularly focusing on the properties and factors of undirected, finite, and simple graphs. It defines key terms such as the order and size of a graph, vertex degree, and the concept of even factors, including the specific case of 2-factors. The section highlights significant contributions to the field, including Tutte’s 1-factor theorem and various conditions established by researchers like Ota and Tokuda, Ryjáček et al., and Zhou et al. for the existence of 2-factors and even factors in different classes of graphs.
Furthermore, the introduction delves into spectral graph theory, defining the adjacency matrix and the signless Laplacian matrix, along with their spectral radii. It references previous work that connects spectral radius conditions to the existence of perfect matchings and even factors in graphs. The paper aims to establish a new sufficient condition related to the signless Laplacian spectral radius for connected graphs of even order, culminating in Theorem 1.1, which provides a specific criterion for the existence of an even factor in such graphs under certain conditions.
Discussion
In the discussion section, the authors present several preliminary lemmas that are crucial for proving the main theorem regarding the existence of even factors in graphs. Notably, Lemma 2.2 establishes a sufficient condition for the existence of even factors by relating the quotient of certain graph structures, while Lemma 2.3 asserts that the quotient of a graph is at least as large as that of its subgraphs, with equality only when the graphs are identical. The section further introduces the concept of equitable partitions of matrices, where the corresponding quotient matrix retains spectral properties of the original matrix, as outlined in Lemmas 2.4 and 2.5.
The proof of Theorem 1.1 is then detailed, demonstrating the connection between the signless Laplacian spectral radius and the presence of even factors. The authors employ a contradiction approach, assuming a graph \( G \) lacks an even factor and deriving inequalities involving the quotient of \( G \) and constructed graphs \( G_1 \), \( G_2 \), and \( G_3 \). The analysis is divided into three cases based on the size of a specific subset \( S \) of vertices, leading to various inequalities that ultimately contradict the initial assumption. The results highlight the intricate relationships between graph structures and their spectral properties, reinforcing the significance of equitable partitions in understanding graph factors.