ملاحظة حول حد داس-موجلال على طاقة الرسم البياني Note on Das-Mojallal Bound on Graph Energy

شارك:
المجلة: match Communications in Mathematical and in Computer Chemistry، المجلد: 97، العدد: 2
DOI: https://doi.org/10.46793/match.97-2.00526
تاريخ النشر: 2026-05-28
المؤلف: Akbar Jahanbani وآخرون
الموضوع الرئيسي: نظرية الرسوم البيانية وتطبيقاتها

نظرة عامة

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

مقدمة

في هذه الفقرة، يناقش المؤلفون المفاهيم الأساسية والترميز المستخدم في تحليلهم لطاقة الرسم، مشيرين إلى الأعمال السابقة. يعرفون رسمًا بسيطًا \( G \) مع مجموعة الرؤوس \( V(G) = \{v_1, v_2, \ldots, v_n\} \) ومجموعة الحواف \( E(G) \)، حيث يتم الإشارة إلى درجة الرأس \( v_i \) على أنها \( d_i \) وأدنى درجة عبر جميع الرؤوس هي \( \delta \). يتم حساب طاقة الرسم، المشار إليها بـ \( E(G) \)، باستخدام القيم الذاتية \( \lambda_1, \lambda_2, \ldots, \lambda_n \) لمصفوفة الجوار، مع التعبير عن الطاقة الكلية على أنها \( E(G) = \sum_{i=1}^{n} |\lambda_i| \).

ينتقد المؤلفون حدًا علويًا تم الادعاء به سابقًا لطاقة الرسم المقدم في النظرية 3.1 من ورقة أخرى، والتي تؤكد أن \( E(G) \leq 2m(n – \delta) + 4m^3(1 – \frac{1}{\omega}) \). يجادلون بأن إثبات هذه المعادلة معيب بسبب الطبيعة غير المحددة للعلاقات بين حواف الرسم وقيمه الذاتية. على وجه التحديد، يبرزون أن المجموعات التي تتضمن القيم الذاتية والحواف تعتمد على تسمية عشوائية للرؤوس، مما يجعلها غير ثابتة وبالتالي يجعل الإثبات غير حاسم. يشير المؤلفون إلى أن هناك تناقضات إضافية في إثبات النظرية 3.1، على الرغم من أنهم لا يوضحون هذه الأمور أكثر في هذه الفقرة.

نقاش

في هذه الفقرة، يحلل المؤلفون عدم المساواة المقدمة في المعادلة (1) ويظهرون أنها شكل أضعف مقارنةً بالحدود العليا الكلاسيكية لمكليلاند، مشيرين بشكل محدد إلى أن \( E(G) \leq \sqrt{2mn} \). تؤكد النظرية 1 أنه بالنسبة لرسم متصل \( G \) مع \( n \) رأسًا، و\( m \) حافة، وأدنى درجة \( \delta \)، وعدد مجموعة \( \omega \)، فإن عدم المساواة \( E(G) \leq \sqrt{2mn} < 2m(n - \delta) + 4m^3(1 - \frac{1}{\omega}) \) صحيحة، مع كون عنصر داس-موجلال صارمًا. يعتمد الإثبات على العلاقة بين عدد الحواف ودرجات الرؤوس، مؤكدًا أن \( \sqrt{2m} > \delta \) ضروري. من خلال اعتبار أن \( 2m \) يساوي مجموع درجات الرؤوس، يستنتج المؤلفون أن تكوين الدرجة الدنيا يحدث عندما تكون جميع الرؤوس بدرجة \( \delta \)، مما يؤدي إلى الشرط \( n > \delta \). نظرًا لأن في الرسوم البسيطة الحد الأقصى للدرجة هو \( n – 1 \)، يتم الوفاء بهذا الشرط، مما يؤكد أن \( 2m(n) + \sqrt{2m} – \delta > \sqrt{2mn} \) ويكمل إثبات النظرية 1.

Journal: match Communications in Mathematical and in Computer Chemistry, Volume: 97, Issue: 2
DOI: https://doi.org/10.46793/match.97-2.00526
Publication Date: 2026-05-28
Author(s): Akbar Jahanbani et al.
Primary Topic: Graph theory and applications

Overview

In their 2013 publication, Das and Mojallal introduced a novel upper bound on graph energy. This section critiques their proof, highlighting its limitations in comparison to McClelland’s established estimate. The authors argue that the bound proposed by Das and Mojallal does not surpass the effectiveness of McClelland’s classic approach, suggesting that the latter remains a more reliable measure for graph energy.

Introduction

In this section, the authors discuss the foundational concepts and notation used in their analysis of graph energy, referencing previous work. They define a simple graph \( G \) with vertex set \( V(G) = \{v_1, v_2, \ldots, v_n\} \) and edge set \( E(G) \), where the degree of vertex \( v_i \) is denoted as \( d_i \) and the minimum degree across all vertices is \( \delta \). The energy of the graph, denoted as \( E(G) \), is calculated using the eigenvalues \( \lambda_1, \lambda_2, \ldots, \lambda_n \) of the adjacency matrix, with the total energy expressed as \( E(G) = \sum_{i=1}^{n} |\lambda_i| \).

The authors critique a previously claimed upper bound for graph energy presented in Theorem 3.1 of another paper, which asserts that \( E(G) \leq 2m(n – \delta) + 4m^3(1 – \frac{1}{\omega}) \). They argue that the proof of this inequality is flawed due to the ill-defined nature of the relationships between the edges of the graph and its eigenvalues. Specifically, they highlight that the sums involving eigenvalues and edges depend on the arbitrary labeling of vertices, making them non-invariant and thus rendering the proof inconclusive. The authors indicate that additional inconsistencies exist in the proof of Theorem 3.1, although they do not elaborate on these further in this section.

Discussion

In this section, the authors analyze the inequality presented in equation (1) and demonstrate that it is a weaker form compared to the classical McClelland upper bounds, specifically stating that \( E(G) \leq \sqrt{2mn} \). Theorem 1 establishes that for a connected graph \( G \) with \( n \) vertices, \( m \) edges, minimum degree \( \delta \), and clique number \( \omega \), the inequality \( E(G) \leq \sqrt{2mn} < 2m(n - \delta) + 4m^3(1 - \frac{1}{\omega}) \) holds true, with the Das-Mojallal component being strict. The proof hinges on the relationship between the number of edges and vertex degrees, asserting that \( \sqrt{2m} > \delta \) is necessary. By considering that \( 2m \) equals the sum of the vertex degrees, the authors derive that the minimal degree configuration occurs when all vertices have degree \( \delta \), leading to the condition \( n > \delta \). Given that in simple graphs the maximum degree is \( n – 1 \), this condition is satisfied, thereby confirming that \( 2m(n) + \sqrt{2m} – \delta > \sqrt{2mn} \) and completing the proof of Theorem 1.