New Bounds on the Energy of Graphs with Self-Loops

Jianping Liu, Yinghuan Chen, Darko Dimitrov, Jinsong ChenMatch 2023 · DOI

Abstract

Let $G_\sigma$ be the graph obtained from a simple graph $G$ of order $n$ by adding $\sigma$ self-loops, one self-loop at each vertex in $S \subseteq V(G)$. Let $\lambda_1(G_\sigma), \lambda_2(G_\sigma), \dots, \lambda_n(G_\sigma)$ be the eigenvalues of $G_\sigma$. The energy of $G_\sigma$, denoted by $\mathcal{E}(G_\sigma)$, is defined as $\mathcal{E}(G_\sigma) = \sum_{i=1}^n |\lambda_i(G_\sigma) - \frac{\sigma}{n}|$. In this paper, using various analytic inequalities and previously established results, we derive several new lower and upper bounds on $\mathcal{E}(G_\sigma)$.

Introduction

In spectral graph theory, the concept of "graph energy" was originally introduced by Ivan Gutman in 1978 to approximate the total $\pi$-electron energy of conjugated hydrocarbon molecules. While traditional graph energy focuses on simple graphs (no loops, no multiple edges), chemistry often requires modeling heteroconjugated molecules—systems where some atoms in a ring are not carbon. In these models, self-loops at specific vertices represent the presence of these heteroatoms.

Recently, a specific definition for the energy of a graph with self-loops ($G_\sigma$) was proposed. However, calculating the exact energy requires finding all eigenvalues of a graph's adjacency matrix, which is computationally expensive for large systems. This paper addresses the need for bounds: simple algebraic formulas that allow researchers to estimate this energy quickly using only basic graph properties such as the number of vertices, edges, loops, and vertex degrees.

Methodology

The authors employ a theoretical approach rooted in spectral graph theory and mathematical analysis. Their primary tools include:

  • Spectral Moments ($M_k$): These are sums of the $k$-th powers of the graph's eigenvalues. The authors derive new relationships between these moments and the total graph energy.
  • Analytic Inequalities: To bridge the gap between known graph parameters and energy, the authors apply several famous mathematical inequalities, including the Cauchy-Schwarz inequality (for upper bounds), the Diaz-Metcalf inequality (to relate vertex degrees to energy), and various absolute value inequalities.
  • Matrix Theory: They analyze the properties of the adjacency matrix $A(G_\sigma)$, which remains real and symmetric even with self-loops, ensuring all eigenvalues are real.

Key Theoretical Insights

A critical adjustment in this work is the modified energy definition: $\mathcal{E}(G_\sigma) = \sum_{i=1}^n |\lambda_i - \frac{\sigma}{n}|$. Subtracting the average loop value ($\sigma/n$) centers the spectrum, making the energy a more meaningful measure of "deviation" or "spread."

The paper demonstrates the power of spectral moments, showing that the $k$-th moment can be bounded from below using only the number of edges ($m$), vertices ($n$), and loops ($\sigma$). Furthermore, one of the most practical insights is the derivation of lower bounds based on the maximum degree ($\Delta$) and minimum degree ($\delta$) of the vertices, linking local connectedness directly to global energy. Most of the derived bounds are designed to collapse back into classical graph energy bounds when $\sigma = 0$, ensuring consistency with existing literature.

Main Results

The paper establishes a series of theorems providing new boundaries for graph energy:

  • Fundamental Lower Bound: Theorem 4 provides a clean lower bound: $\mathcal{E}(G_\sigma) \geq \sqrt{2m + \sigma - \frac{\sigma^2}{n}}$. This gives a quick "floor" for energy based only on the count of edges and loops.
  • Graph Spread Relationship: Theorem 6 relates energy to the "graph spread" ($s(G_\sigma) = \lambda_1 - \lambda_n$), demonstrating that as the gap between the largest and smallest eigenvalue grows, the minimum possible energy also increases.
  • Spectral Radius and Degree Bounds: Theorems 8 and 9 provide new upper bounds that incorporate the maximum vertex degree ($\Delta$), offering tighter estimates for graphs with non-uniform connectivity.

Conclusion and Future Work

While the authors establish several "sharp" bounds (where equality holds for specific graph classes), many complex bounds may be loose for certain families of graphs. Future work should involve chemical validation—comparing these mathematical frameworks against experimental data (e.g., heat of formation) to identify the best predictors of physical properties. Additionally, investigating these bounds for other graph matrices, such as the Laplacian or signless Laplacian, remains a promising direction for further research.

Summary updated

Abstract

Let Gσ be the graph obtained from a simple graph G of order n by adding σ self-loops, one self-loop at each vertex in S ⊆ V (G).Let λ1(Gσ), λ2(Gσ), . . ., λn(Gσ) be the eigenvalues of Gσ.The energy of Gσ, denoted by E (Gσ), is defined as E (Gσ) = n i=1 λi(Gσ) -σ n .In this paper, using various analytic inequalities and previously established results, we derive several new lower and upper bounds on E (Gσ).
BibTeX
@inproceedings{liu2023new,
  author = {Jianping Liu and Yinghuan Chen and Darko Dimitrov and Jinsong Chen},
  title = {{New Bounds on the Energy of Graphs with Self-Loops}},
  booktitle = {Match},
  year = {2023},
  doi = {10.46793/match.91-3.779l},
}
Figure