DOI: https://doi.org/10.61091/jcmcc130-18
تاريخ النشر: 2026-05-09
المؤلف: Shunya Tamura
الموضوع الرئيسي: نظرية الرسوم البيانية وتطبيقاتها
نظرة عامة
في هذه الورقة، يقوم المؤلفون بالتحقيق في الرسوم البيانية الدائرية المشتقة من الرسم البياني الكامل \( K_N \) عن طريق إزالة الحواف المرتبطة بفئة مسافة محددة. يقومون بتحليل الخصائص الرئيسية للرسم البياني مثل المقاومة الفعالة، ووقت الاصطدام المتوقع، وعدد الأشجار الممتدة، وعدد الغابات الممتدة ذات المكونين، باستخدام تمثيلات طيفية تعتمد على القيم الذاتية لمصفوفة لابلاس. بينما تؤدي عمليات الحذف العامة لفئة المسافة إلى تمثيلات طيفية، فإن الأشكال المغلقة عادة ما تكون بعيدة المنال. تركز الدراسة على الحالات التي يتم فيها حذف فئة مسافة واحدة، وخاصة عندما يكون عدد الرؤوس \( N \) فرديًا و \( \text{gcd}(r, N) = 1 \)، مما يوضح أن الرسم البياني \( G_{N,r} \) متشابه هيكليًا مع \( G_{N,1} \). يؤدي ذلك إلى صيغ صريحة من نوع الأس للجهد الفعال والأشجار الممتدة، مع تعبيرات مغلقة للغابات الممتدة ذات المكونين وأوقات الاصطدام المتوقعة.
يبرز المؤلفون أن حالة \( r = 2 \) ليست متميزة جوهريًا ولكنها نتيجة لبنية التماثل الأساسية. يربطون نتائجهم بالعمل السابق على الرسم البياني الكامل مع دورة هاملتونية تمت إزالتها، مما يوفر اشتقاقًا طيفيًا موحدًا. مع اقتراب \( N \) من اللانهاية، يتقارب نسبة عدد الأشجار الممتدة في \( G_{N,1} \) إلى تلك الموجودة في \( K_N \) إلى \( e^{-2} \). تختتم الورقة بالإشارة إلى أنه بينما يؤدي حذف فئة المسافة إلى تغييرات كبيرة في الخصائص الطيفية والتركيبية، قد لا تؤدي السيناريوهات الأكثر تعقيدًا التي تشمل فئات مسافة متعددة أو عندما يكون \( \text{gcd}(r, N) > 1 \) إلى أشكال مغلقة مماثلة، مما يقترح مجالات للبحث المستقبلي في هذه المجالات.
مقدمة
تناقش مقدمة الورقة مفهوم المقاومة الفعالة في الرسوم البيانية، مع تسليط الضوء على أهميتها عبر مجالات مختلفة مثل نظرية الشبكات الكهربائية ونظرية الرسوم البيانية الطيفية. ترتبط المقاومة الفعالة بوقت الاصطدام المتوقع للمشي العشوائي وعدد الأشجار الممتدة من خلال نظرية مصفوفة كيرشوف. يركز المؤلفون على الرسوم البيانية الدائرية المشتقة من الرسم البياني الكامل \( K_N \) عن طريق إزالة الحواف من فئة مسافة محددة، والتي يشار إليها بـ \( G_{N,r} \). تهدف هذه الدراسة إلى فهم كيفية تغير الخصائص الطيفية والتركيبية مع التعديلات المحلية البسيطة على الرسوم البيانية المتناظرة بشكل كبير.
تشمل النتائج الرئيسية تعبيرات صريحة للمقاومة الفعالة، وأوقات الاصطدام المتوقعة، وعدد الأشجار الممتدة لأبسط حالة لفئة مسافة واحدة محذوفة عندما يكون \( \text{gcd}(r, N) = 1 \). على وجه التحديد، بالنسبة لـ \( N \) فردي، يتم اشتقاق المقاومة الفعالة \( R^{(1)}(u, v) \) وعدد الأشجار الممتدة \( \tau(G_{N,1}) \) في أشكال مغلقة. كما يثبت المؤلفون أن خصائص \( G_{N,r} \) متشابهة هيكليًا مع تلك الخاصة بـ \( G_{N,1} \) تحت ظروف معينة، مما يؤدي إلى نتائج مماثلة لقيم مختلفة من \( r \). تختتم الورقة بنتائج حدية تشير إلى أنه مع اقتراب \( N \) من اللانهاية، تتصرف المقاومة الفعالة بشكل مشابه لتلك الخاصة بالرسم البياني الكامل، بينما يتقارب عدد الأشجار الممتدة إلى حد معين.
النتائج
في هذا القسم، يثبت المؤلفون نتائج أساسية تتعلق بخصائص رسم بياني غير موجه وزني \( G_{N,w} \) محدد على مجموعة رؤوس تتوافق مع المجموعة الدائرية \( V = \mathbb{Z}_N \). يتم تقديم الفرق الموجه \( q(u, v) \) والمسافة الدائرية غير الموجهة \( h(u, v) \)، مع تسليط الضوء على أدوارها المتميزة في التحليل الطيفي ونظرية الرسوم البيانية. يتم التأكيد على الاتصال في \( G_{N,w} \)، مع الشرط أن جميع القيم الذاتية لمصفوفة لابلاس غير الصفرية \( \lambda_j > 0 \) لـ \( 1 \leq j \leq N-1 \). يتم اشتقاق القيم الذاتية لمصفوفة لابلاس \( L \)، مما يظهر أن \( \lambda_j \) يمكن التعبير عنها من حيث دالة الوزن \( w(k) \) ودالة جيب التمام.
تشمل النتائج الرئيسية التمثيل الطيفي للمقاومة الفعالة \( R(u, v) \) من حيث القيم الذاتية \( \lambda_j \) والبقايا الموجهة \( q(u, v) \)، بالإضافة إلى العلاقة بين عدد الأشجار الممتدة الوزنية \( \tau(G_{N,w}) \) والقيم الذاتية. يقدم المؤلفون أيضًا نظرية تربط عدد الغابات الممتدة ذات المكونين \( F(u | v) \) بالمقاومة الفعالة، ويشتقون صيغة لوقت الاصطدام المتوقع \( H(u, v) \) في سياق مشي عشوائي على \( G_{N,w} \). من الجدير بالذكر أن التماثل \( H(u, v) = H(v, u) \) يتم إثباته من خلال تلقائية الرسم البياني، مما يعزز الخصائص الهيكلية للرسم البياني.
مناقشة
في هذا القسم، يستكشف المؤلفون الخصائص الطيفية للرسوم البيانية الدائرية المشتقة من الرسم البياني الكامل \( K_N \) عن طريق حذف الحواف المرتبطة بفئات مسافة محددة. يثبتون أن المقاومة الفعالة \( R(u, v) \)، وأوقات الاصطدام المتوقعة \( H(u, v) \)، وعدد الأشجار الممتدة \( \tau(G_{N,S}) \)، وعدد الغابات الممتدة ذات المكونين يمكن التعبير عنها بشكل موحد من خلال القيم الذاتية لمصفوفات الرسوم البيانية المعدلة. بالنسبة لفئة مسافة واحدة محذوفة حيث \( \gcd(r, N) = 1 \)، يوضح المؤلفون أن الرسم البياني \( G_{N,r} \) متشابه هيكليًا مع \( G_{N,1} \)، مما يسمح باشتقاق أشكال مغلقة لهذه الكميات، خاصة عندما يكون \( N \) فرديًا.
تكشف التحليلات أن القيم الذاتية تعكس بنية الرسم البياني، مع إزالة فئات المسافة التي تؤدي إلى شكل متعدد الحدود أكثر تعقيدًا. يشتق المؤلفون صيغًا صريحة للمقاومة الفعالة وعدد الأشجار الممتدة، مؤكدين أنه بينما تتصرف مسافة المقاومة بشكل مشابه لتلك الموجودة في الرسم البياني الكامل، فإن عدد الأشجار الممتدة ينخفض بشكل أسي عند إزالة الحواف. يختتمون بالقول إنه بينما توفر نتائجهم فهمًا شاملاً لحالة فئة مسافة واحدة محذوفة، هناك حاجة إلى مزيد من التحقيق في السيناريوهات الأكثر تعقيدًا التي تشمل عمليات حذف متعددة أو شروط gcd مختلفة، والتي قد تؤدي إلى سلوك طيفي مختلف بشكل كبير. تشمل اتجاهات البحث المستقبلية دراسة هياكل القيم الذاتية تحت هذه الظروف الأكثر تعقيدًا واستكشاف ظواهر مماثلة في عائلات الرسوم البيانية المتناظرة الأخرى.
DOI: https://doi.org/10.61091/jcmcc130-18
Publication Date: 2026-05-09
Author(s): Shunya Tamura
Primary Topic: Graph theory and applications
Overview
In this paper, the authors investigate circulant graphs derived from the complete graph \( K_N \) by removing edges associated with a specified distance class. They analyze key graph properties such as effective resistance, expected hitting time, the number of spanning trees, and the number of two-component spanning forests, utilizing spectral representations based on Laplacian eigenvalues. While general distance-class deletions yield spectral representations, closed forms are typically elusive. The study focuses on cases where a single distance class is deleted, particularly when the number of vertices \( N \) is odd and \( \text{gcd}(r, N) = 1 \), demonstrating that the graph \( G_{N,r} \) is isomorphic to \( G_{N,1} \). This leads to explicit exponential-type formulas for effective resistance and spanning trees, with closed expressions for two-component spanning forests and expected hitting times.
The authors highlight that the case of \( r = 2 \) is not fundamentally distinct but rather a consequence of the underlying isomorphism structure. They relate their findings to previous work on the complete graph with a Hamiltonian cycle removed, providing a unified spectral derivation. As \( N \) approaches infinity, the ratio of the number of spanning trees in \( G_{N,1} \) to that in \( K_N \) converges to \( e^{-2} \). The paper concludes by noting that while the deletion of a distance class leads to significant changes in spectral and combinatorial properties, more complex scenarios involving multiple distance classes or when \( \text{gcd}(r, N) > 1 \) may not yield similar closed forms, suggesting avenues for future research in these areas.
Introduction
The introduction of the paper discusses the concept of effective resistance in graphs, highlighting its significance across various fields such as electrical network theory and spectral graph theory. The effective resistance is linked to the expected hitting time of random walks and the enumeration of spanning trees through Kirchhoff’s matrix-tree theorem. The authors focus on circulant graphs derived from the complete graph \( K_N \) by removing edges of a specified distance class, denoted as \( G_{N,r} \). This study aims to understand how spectral and combinatorial properties change with minimal local modifications to highly symmetric graphs.
The main findings include explicit expressions for effective resistance, expected hitting times, and the number of spanning trees for the simplest case of a single deleted distance class when \( \text{gcd}(r, N) = 1 \). Specifically, for odd \( N \), the effective resistance \( R^{(1)}(u, v) \) and the number of spanning trees \( \tau(G_{N,1}) \) are derived in closed forms. The authors also establish that the properties of \( G_{N,r} \) are isomorphic to those of \( G_{N,1} \) under certain conditions, leading to similar results for different values of \( r \). The paper concludes with asymptotic results indicating that as \( N \) approaches infinity, the effective resistance behaves similarly to that of the complete graph, while the number of spanning trees converges to a specific limit.
Results
In this section, the authors establish foundational results regarding the properties of a weighted undirected graph \( G_{N,w} \) defined on a vertex set corresponding to the cyclic group \( V = \mathbb{Z}_N \). The oriented difference \( q(u, v) \) and the unoriented circulant distance \( h(u, v) \) are introduced, highlighting their distinct roles in spectral analysis and graph theory. The connectivity of \( G_{N,w} \) is emphasized, with the condition that all nonzero Laplacian eigenvalues \( \lambda_j > 0 \) for \( 1 \leq j \leq N-1 \). The eigenvalues of the Laplacian matrix \( L \) are derived, showing that \( \lambda_j \) can be expressed in terms of the weight function \( w(k) \) and the cosine function.
Key results include the spectral representation of effective resistance \( R(u, v) \) in terms of the eigenvalues \( \lambda_j \) and the oriented residue \( q(u, v) \), as well as the relationship between the number of weighted spanning trees \( \tau(G_{N,w}) \) and the eigenvalues. The authors also present a theorem connecting the number of two-component spanning forests \( F(u | v) \) to the effective resistance, and they derive a formula for the expected hitting time \( H(u, v) \) in the context of a random walk on \( G_{N,w} \). Notably, the symmetry \( H(u, v) = H(v, u) \) is established through a graph automorphism, reinforcing the structural properties of the graph.
Discussion
In this section, the authors explore the spectral properties of circulant graphs derived from the complete graph \( K_N \) by deleting edges corresponding to specific distance classes. They establish that the effective resistance \( R(u, v) \), expected hitting times \( H(u, v) \), spanning tree counts \( \tau(G_{N,S}) \), and two-component spanning forest counts can be expressed uniformly through the Laplacian eigenvalues of the modified graphs. For a single deleted distance class where \( \gcd(r, N) = 1 \), the authors demonstrate that the graph \( G_{N,r} \) is isomorphic to \( G_{N,1} \), allowing for the derivation of closed forms for these quantities, particularly when \( N \) is odd.
The analysis reveals that the eigenvalues reflect the structure of the graph, with the removal of distance classes leading to a more complex polynomial form. The authors derive explicit formulas for the effective resistance and the number of spanning trees, emphasizing that while the resistance distance behaves similarly to that in the complete graph, the number of spanning trees decreases exponentially when edges are removed. They conclude that while their findings provide a comprehensive understanding for the case of a single deleted distance class, further investigation is needed for more complex scenarios involving multiple deletions or different gcd conditions, which may lead to significantly different spectral behaviors. Future research directions include examining the eigenvalue structures under these more complex conditions and exploring similar phenomena in other symmetric graph families.
