Note on the energy of regular graphs

By Xueliang Li, Yiyang Li, Yongtang Shi. 2009

60 citations recorded by the source corpus.

Abstract For a simple graph G , the energy E ( 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 E ( G ) ⩽ λ 1 + ( n - 1 ) ( 2 m - λ 1 ) , where λ 1 is the spectral radius. If G is k -regular, we have E ( G ) ⩽ k + k ( n - 1 ) ( n - k ) . Denote E 0 = k + k ( n - 1 ) ( n - k ) . Balakrishnan [R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287–295] proved that for each ϵ > 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 E ( G ) E 0 ϵ , and proposed an open problem that, given a positive integer n ⩾ 3 , and ϵ > 0 , does there exist a k -regular graph G of order n such that E ( G ) E 0 > 1 - ϵ . In this paper, we show that for each ϵ > 0 , there exist infinitely many such n that E ( G ) E 0 > 1 - ϵ . Moreover, we construct another class of simpler graphs which also supports the first assertion that E ( G ) E 0 ϵ .

Subfields: Computational Theory and Mathematics, Geometry and Topology, Organic Chemistry

View Paper: https://www.semanticscholar.org/paper/244c742300b8128a8c81747b4f1007e43a9e65e6