حول طيف هامينغ وطاقة هامينغ للرسوم البيانية On the Hamming Spectrum and Hamming Energy of Graphs

شارك:
المجلة: Discrete Mathematics Letters
DOI: https://doi.org/10.47443/dml.2026.014
تاريخ النشر: 2026-04-12
المؤلف: Bojana Borovićanin وآخرون
الموضوع الرئيسي: نظرية الرسوم البيانية وتطبيقاتها

نظرة عامة

في هذا البحث، يستقصي المؤلفون الخصائص الطيفية لمصفوفة هامينغ \( H(G) \) المرتبطة بالرسم البياني البسيط \( G \). تُعرّف هذه المصفوفة من خلال المسافات الهامينية لسلاسل ثنائية مستمدة من مصفوفة الحدوث للرسم البياني، مما يقدم نهجًا جديدًا لفهم نظرية الرسوم البيانية الطيفية والكيميائية. establishes الدراسة حدودًا عليا وسفلى لأكبر وأصغر القيم الذاتية لمصفوفة هامينغ بشكل خاص للطرق، وتوفر تعبيرات مغلقة للصيغة الطيفية لهامينغ وطاقة هامينغ للرسوم البيانية المنتظمة، بما في ذلك الدورات، والمكملات، ورسومها الخطية، فيما يتعلق بالطيف المجاور الكلاسيكي.

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

مقدمة

تناقش مقدمة الورقة أهمية الأطياف الرسومية في فهم الخصائص الهيكلية والديناميات للرسوم البيانية، مع تطبيقات عبر مجالات مختلفة مثل الكيمياء، والفيزياء، وعلوم الحاسوب. تُعرّف الرسم البياني البسيط \( G = (V(G), E(G)) \) مع \( n \) من الرؤوس و \( m \) من الحواف، مقدمةً مفاهيم رئيسية مثل تلاصق الرؤوس، ودرجة الرأس \( d_G(v) \)، ورسم الخط \( L(G) \). كما يقدم المؤلفون مصفوفة التلاصق \( A(G) \) ومصفوفة الحدوث \( B(G) \)، مما يؤدي إلى تعريف مؤشر هامينغ \( H_B(G) \) ومصفوفة هامينغ \( H(G) \). يتم تأسيس العلاقة بين مؤشر H ومصفوفة H، مع تسليط الضوء على التمييز بين القيم الذاتية A والقيم الذاتية H، بالإضافة إلى أطيافها الخاصة.

تؤكد الورقة على المجال الناشئ لطاقة هامينغ، التي تُعرّف على أنها مجموع القيم المطلقة للقيم الذاتية H، وارتباطها بالخصائص الفيزيائية الكيميائية، مما يشير إلى أن طاقة H قد توفر قوة تنبؤية أفضل من طاقة الرسم البياني التقليدية. يهدف المؤلفون إلى استكشاف الخصائص الطيفية لمصفوفة هامينغ، مع التركيز بشكل خاص على الحدود العليا والسفلى للقيم الذاتية H في الرسوم البيانية الخطية والرسوم البيانية المنتظمة. كما يعتزمون التحقيق في العلاقة بين الطيف H والمعلمات الطيفية الكلاسيكية، مما يشير إلى أن هذا المجال لا يزال غير مستكشف ويحتفظ بأهمية رياضية مستقلة. تعد الأقسام اللاحقة بتقديم نتائج نظرية حول الأطياف H وطاقة H، بما في ذلك تقديرات القيم الذاتية والمقارنات مع مقاييس الطيف A.

نقاش

في هذا القسم، يقدم المؤلفون تعريفات أساسية ونظريات حاسمة لأبحاثهم حول مصفوفات هامينغ المرتبطة بالرسوم البيانية. تؤسس النظرية 2.1 علاقة بين درجات الرؤوس في الرسم البياني $G$ والمسافة الهامينية، بينما يتم استكشاف خصائص مصفوفة هامينغ $H(G)$، مما يكشف عنها كمصفوفة حقيقية متناظرة غير سالبة ذات خصائص طيفية محددة. يعرف المؤلفون المصفوفات غير القابلة للاختزال ويظهرون أن مصفوفات هامينغ لمعظم الرسوم البيانية غير قابلة للاختزال، باستثناء الحالات التافهة مثل $nK_1$ أو $K_2$. توضح النظريات 2.2 إلى 2.6 المزيد من الخصائص الطيفية للمصفوفات غير السالبة غير القابلة للاختزال، مع التأكيد على أنه يمكن تقدير أكبر قيمة ذاتية لمصفوفة هامينغ من حيث مؤشر هامينغ للرسم البياني.

بالإضافة إلى ذلك، يناقش المؤلفون كثير الحدود المميز H للرسوم البيانية المنتظمة $r$ ومكملاتها، مقدّمين صيغة تربط بين الاثنين. تشير النتائج إلى أن طيف مصفوفة هامينغ مرتبط ارتباطًا وثيقًا بالخصائص الهيكلية للرسم البياني، خاصة في الرسوم البيانية المنتظمة. يضع هذا القسم الأساس للتحليلات والتطبيقات اللاحقة لهذه النتائج النظرية في فهم خصائص الرسوم البيانية من خلال مصفوفات هامينغ الخاصة بها.

Journal: Discrete Mathematics Letters
DOI: https://doi.org/10.47443/dml.2026.014
Publication Date: 2026-04-12
Author(s): Bojana Borovićanin et al.
Primary Topic: Graph theory and applications

Overview

In this research, the authors investigate the spectral properties of the Hamming matrix \( H(G) \) associated with a simple graph \( G \). This matrix, defined through the Hamming distances of binary strings derived from the graph’s incidence matrix, presents a novel approach to understanding spectral and chemical graph theory. The study establishes upper and lower bounds for the largest and smallest eigenvalues of the Hamming matrix specifically for paths, and it provides closed-form expressions for the Hamming spectrum and Hamming energy of regular graphs, including cycles, their complements, and their line graphs, in relation to the classical adjacency spectrum.

Additionally, the authors present a factorization that connects the characteristic polynomial of the Hamming matrix of a regular graph to those of its complement and line graph. These findings enhance the understanding of the interplay between Hamming-based invariants and traditional spectral quantities, contributing to the broader field of spectral graph theory.

Introduction

The introduction of the paper discusses the significance of graph spectra in understanding the structural properties and dynamics of graphs, with applications across various fields such as chemistry, physics, and computer science. It defines a simple graph \( G = (V(G), E(G)) \) with \( n \) vertices and \( m \) edges, introducing key concepts such as vertex adjacency, vertex degree \( d_G(v) \), and the line graph \( L(G) \). The authors also introduce the adjacency matrix \( A(G) \) and the incidence matrix \( B(G) \), leading to the definition of the Hamming index \( H_B(G) \) and the Hamming matrix \( H(G) \). The relationship between the H-index and the H-matrix is established, highlighting the distinction between A-eigenvalues and H-eigenvalues, as well as their respective spectra.

The paper emphasizes the emerging field of Hamming energy, defined as the sum of the absolute values of H-eigenvalues, and its correlation with physicochemical properties, suggesting that H-energy may provide better predictive power than traditional graph energy. The authors aim to explore the spectral properties of the Hamming matrix, particularly focusing on upper and lower bounds for H-eigenvalues in path graphs and regular graphs. They also intend to investigate the relationship between the H-spectrum and classical spectral parameters, indicating that this area remains underexplored and holds independent mathematical interest. The subsequent sections promise to present theoretical results on H-spectra and H-energy, including eigenvalue estimates and comparisons with A-spectral measures.

Discussion

In this section, the authors present foundational definitions and theorems critical to their research on Hamming matrices associated with graphs. Theorem 2.1 establishes a relationship between the degrees of vertices in a graph $G$ and the Hamming distance, while the properties of the Hamming matrix $H(G)$ are explored, revealing it as a real symmetric non-negative matrix with specific spectral characteristics. The authors define irreducible matrices and demonstrate that the Hamming matrices of almost all graphs are irreducible, except in trivial cases such as $nK_1$ or $K_2$. Theorems 2.2 through 2.6 further elucidate the spectral properties of irreducible non-negative matrices, emphasizing that the largest eigenvalue of the Hamming matrix can be estimated in terms of the graph’s Hamming index.

Additionally, the authors discuss the H-characteristic polynomial of $r$-regular graphs and their complements, providing a formula that relates the two. The results indicate that the spectrum of the Hamming matrix is closely linked to the structural properties of the graph, particularly in regular graphs. This section lays the groundwork for subsequent analyses and applications of these theoretical findings in understanding graph properties through their Hamming matrices.