2009/09/22 by Xueliang Li, Yiyang Li, Li, Xueliang +3
Mathematics · #05C50 #05C90 #15A18 #92E10 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C50 #msc:05C90 #msc:15A18 #msc:92E10
paper · pdf · doi:10.48550/arxiv.0909.3910
4 pages
arxiv created 2009/09/22 · arxiv updated 2009/12/01
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)(2m-λ1)), where λ1 is the spectral radius. If G is k-regular, we have E(G)≤ k+√(k(n-1)(n-k)). Denote E0=k+√(k(n-1)(n-k)). Balakrishnan [\it Linear Algebra Appl. \bf 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))/(E0)<ε, 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))/(E0)>1-ε. In this paper, we show that for each ε>0, there exist infinitely many such n that (E(G))/(E0)>1-ε. Moreover, we construct another class of simpler graphs which also supports the first assertion that (E(G))/(E0)<ε.