Note on the energy of regular graphs

作者：Li Xueliang^*; Li Yiyang; Shi Yongtang

来源：Linear Algebra and Its Applications, 2010, 432(5): 1144-1146.

DOI：10.1016/j.laa.2009.10.023

• Graph energy
• Regular graph
• Paley graph
• Open problem

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

• 出版日期2010-2-15
• 单位南开大学