Note on the energy of regular graphs

DOI10.1016/J.LAA.2009.10.023MaRDI QIDQ847201zbMATH OpenOpenAlexFDO

Authors Xueliang Li, Yongtang Shi, Yiyang Li

Publication date 12 February 2010

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.3910

zbMATH Keywords

Paley graphregular graphgraph energyopen problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Applications of graph theory (05C90) Eigenvalues, singular values, and eigenvectors (15A18) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Abstract: For a simple graph $G$, the energy $mathcalE(G)$ is defined as the sum of the absolute values of all the eigenvalues of its adjacency matrix $A(G)$. Let $n,m$, respectively, be the number of vertices and edges of $G$. One well-known inequality is that $mathcalE(G)leqlambd{a}_1+sqrt(n-1)(2m-lambd{a}_1)$, where $lambd{a}_1$ is the spectral radius. If $G$ is $k$-regular, we have $mathcalE(G)leqk+sqrtk(n-1)(n-k)$. Denote $mathcal{E}_0=k+sqrtk(n-1)(n-k)$. Balakrishnan [{it Linear Algebra Appl.} {�f 387} (2004) 287--295] proved that for each $epsilon>0$, there exist infinitely many $n$ for each of which there exists a $k$-regular graph $G$ of order $n$ with $k<n-1$ and $fracmathcalE(G)mathcal{E}_0<epsilon$, and proposed an open problem that, given a positive integer $ngeq3$, and $epsilon>0$, does there exist a $k$-regular graph $G$ of order $n$ such that $fracmathcalE(G)mathcal{E}_0>1-epsilon$. In this paper, we show that for each $epsilon>0$, there exist infinitely many such $n$ that $fracmathcalE(G)mathcal{E}_0>1-epsilon$. Moreover, we construct another class of simpler graphs which also supports the first assertion that $fracmathcalE(G)mathcal{E}_0<epsilon$.

Recommendations

• Remarks on the energy of regular graphs
• The energy of a graph
• On the energy of regular graphs
• scientific article; zbMATH DE number 7250388
• On the energy of complement of regular line graphs

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1618184 (Why is no real title available?)
• A note on energy of some graphs
• Analysis of Complex Networks
• Applications of a theorem by Ky Fan in the theory of graph energy
• Graph theory
• Laplacian energy of a graph
• On the average energy of circulant graphs
• On the energy of complement of regular line graphs
• On the energy of regular graphs
• On the energy of unitary Cayley graphs
• The energy of a graph
• The energy of unitary Cayley graphs

Cited in

(12)

• On the energy of regular graphs
• The energy of a graph
• LOWER BOUNDS FOR ENERGY OF MATRICES AND ENERGY OF REGULAR GRAPHS
• On the difference of energies of a graph and its complement graph
• On the minimum energy of regular graphs
• Regular graphs with maximal energy per vertex
• The general connectivity indices of fluoranthene-type benzenoid systems
• scientific article; zbMATH DE number 5656442 (Why is no real title available?)
• Integral circulant graphs of prime power order with maximal energy
• Remarks on the energy of regular graphs
• Numerous graph energies of regular subdivision graph and complete graph
• Closed and asymptotic formulas for energy of some circulant graphs

This page was built for publication: Note on the energy of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q847201)