DOI: https://doi.org/10.55630/mem.2026.55.078-084
تاريخ النشر: 2026-05-19
المؤلف: Kristiyan Vasilev
الموضوع الرئيسي: الحدود والهياكل في نظرية الرسوم البيانية
نظرة عامة
تتناول هذه الملاحظة البحثية نوعًا محددًا من مشكلة الحافة-الإيزوبيريمتريك المتعلقة بقوى الرسوم البيانية الدائرية، والتي يشار إليها بـ \( C_s^n \). النتيجة الرئيسية هي أنه بالنسبة لمجموعة من الرؤوس بحجم \( k \)، يتم تحقيق الحد الأقصى لعدد الحواف الناتجة من خلال اختيار \( k \) من الرؤوس المتتالية من الرسم البياني الدائري. تسهم هذه النتيجة في فهم الاتصال بالحواف والبنية داخل الرسوم البيانية الدائرية، مما يوفر حلاً واضحًا للمشكلة المطروحة.
مقدمة
في هذا القسم، يتناول المؤلفون مشكلة الحافة-الإيزوبيريمتريك للرسوم البيانية غير الموجهة البسيطة، مع التركيز بشكل خاص على الحد الأقصى لعدد الحواف في رسم بياني فرعي ناتج عن رسم بياني \( G \) يحتوي على \( k \) من الرؤوس. يتم صياغة المشكلة على أنها إيجاد \( \max |U|=k, U \subset V e(U) \)، حيث \( e(U) \) تشير إلى عدد الحواف بين المجموعة الفرعية \( U \) ومكملها. يبرز المؤلفون أنه بالنسبة للرسوم البيانية المنتظمة \( d \)، فإن المجموعات المثلى هي تلك التي لها أصغر محيط. يقدمون نتيجة مهمة لقوة \( s \) من الرسوم البيانية الدائرية \( C_n^s \)، حيث يثبتون أنه بالنسبة للأعداد الصحيحة الموجبة \( n \)، \( k \)، و \( s \) (مع \( n \geq k \) و \( n > s \))، يتم تحقيق الحد الأقصى لعدد الحواف بواسطة أي مجموعة من \( k \) من الرؤوس المتتالية.
كما يشير المؤلفون إلى أنه إذا كان \( s \geq n/2 \)، فإن الرسم البياني يتصرف مثل رسم بياني كامل \( K_n \)، مما يسمح لهم بتقييد تحليلهم للحالة التي يكون فيها \( s < n/2 \). يفترضون \( k \geq s + 2 \) لتبسيط نتائجهم، حيث أن القيم الأصغر لـ \( k \) تؤدي إلى حلول مثلى بسيطة. بينما تؤكد النظرية 1 وجود المحسنات، فإن تصنيف هذه المحسنات لا يزال سؤالًا مفتوحًا، كما يتضح من مثال مع معلمات محددة. يعترف المؤلفون بأن نتيجة مماثلة تم الحصول عليها بشكل مستقل من قبل باحثين آخرين، على الرغم من أن برهانهم يختلف في النهج.
مناقشة
في هذا القسم، يناقش المؤلفون تطبيق نظرية توران والأساليب الطيفية لاستنتاج حدود على عدد الحواف في الرسوم البيانية الفرعية للرسم البياني الدائري \( C_s^n \). يقدمون نظام ترميز يربط بين رؤوس \( C_s^n \) وعناصر من \( \mathbb{Z}/n\mathbb{Z} \) ويعرفون مقاييس المسافة المختلفة. يثبت المؤلفون أن عدد الكليكة \( \omega(C_s^n) = s + 1 \) ويطبقون نظرية توران لاستنتاج حد على الحد الأقصى لعدد الحواف في مجموعة \( U \) من الرؤوس، مما يؤدي إلى النتيجة الفرعية التي تفيد بأنه بالنسبة لـ \( k \geq s + 2 \)، فإن الحد الأقصى لعدد الحواف \( e(U) \) يحقق \( e(U) \leq \frac{sk^2}{2(s + 1)} + O(k) \).
بالإضافة إلى ذلك، يستخدم المؤلفون الحدود الطيفية المستمدة من مصفوفة التلاصق للرسم البياني. يقدمون عدة ليمات تربط بين عدد الحواف والقيم الذاتية لمصفوفة التلاصق، مما يؤدي في النهاية إلى نتيجة فرعية توفر حدًا أعلى على \( e(U) \) من حيث حجم \( U \) وأكبر قيمة ذاتية ثانية. كما تم تقديم مقارنة عددية، توضح أنه بينما يكون الحد الطيفي قريبًا من الحد الأقصى الدقيق لبعض الأنظمة، فإنه يفشل في تقدير الحد الأقصى بدقة عندما يكون كل من \( k \) و \( s \) كبيرين، خاصة عندما يكون \( k/s \gtrsim 2 \). يختتم القسم بتحليل مفصل لبنية المجموعات الفرعية \( U \) وعدد حوافها، مما يعزز الحدود التي تم تأسيسها.
DOI: https://doi.org/10.55630/mem.2026.55.078-084
Publication Date: 2026-05-19
Author(s): Kristiyan Vasilev
Primary Topic: Limits and Structures in Graph Theory
Overview
This research note addresses a specific variant of the edge-isoperimetric problem concerning powers of cycle graphs, denoted as \( C_s^n \). The primary finding is that for a vertex subset of size \( k \), the maximum number of edges induced is attained by selecting \( k \) consecutive vertices from the cycle graph. This result contributes to the understanding of edge connectivity and structure within cycle graphs, providing a clear solution to the posed problem.
Introduction
In this section, the authors address the edge-isoperimetric problem for simple undirected graphs, specifically focusing on the maximum number of edges in an induced subgraph of a graph \( G \) with \( k \) vertices. The problem is framed as finding \( \max |U|=k, U \subset V e(U) \), where \( e(U) \) denotes the number of edges between the subset \( U \) and its complement. The authors highlight that for \( d \)-regular graphs, the optimal subsets are those with the smallest perimeter. They present a significant result for the \( s \)-th power of cycle graphs \( C_n^s \), establishing that for positive integers \( n \), \( k \), and \( s \) (with \( n \geq k \) and \( n > s \)), the maximum number of edges is achieved by any set of \( k \) consecutive vertices.
The authors also note that if \( s \geq n/2 \), the graph behaves like a complete graph \( K_n \), allowing them to restrict their analysis to the case where \( s < n/2 \). They assume \( k \geq s + 2 \) to simplify their findings, as smaller values of \( k \) yield straightforward optimal solutions. While Theorem 1 confirms the existence of maximizers, the classification of these maximizers remains an open question, as illustrated by an example with specific parameters. The authors acknowledge that a similar result was independently obtained by other researchers, although their proof differs in approach.
Discussion
In this section, the authors discuss the application of Turán’s theorem and spectral methods to derive bounds on the number of edges in subgraphs of the cyclic graph \( C_s^n \). They introduce a notation system that associates vertices of \( C_s^n \) with elements of \( \mathbb{Z}/n\mathbb{Z} \) and define various distance metrics. The authors establish that the clique number \( \omega(C_s^n) = s + 1 \) and apply Turán’s theorem to derive a bound on the maximum number of edges in a subset \( U \) of vertices, leading to the corollary that for \( k \geq s + 2 \), the maximum number of edges \( e(U) \) satisfies \( e(U) \leq \frac{sk^2}{2(s + 1)} + O(k) \).
Additionally, the authors utilize spectral bounds derived from the adjacency matrix of the graph. They present several lemmas that relate the number of edges to the eigenvalues of the adjacency matrix, ultimately yielding a corollary that provides an upper bound on \( e(U) \) in terms of the size of \( U \) and the second largest eigenvalue. A numerical comparison is also provided, illustrating that while the spectral bound is close to the exact maximum for certain regimes, it fails to accurately approximate the maximum when both \( k \) and \( s \) are large, particularly when \( k/s \gtrsim 2 \). The section concludes with a detailed analysis of the structure of subsets \( U \) and their edge counts, reinforcing the established bounds.
