Note on the energy of regular graphs - Mathematics > CombinatoricsReport as inadecuate




Note on the energy of regular graphs - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: For a simple graph $G$, the energy $\mathcal{E}G$ is defined as the sum ofthe absolute values of all the eigenvalues of its adjacency matrix $AG$. Let$n, m$, respectively, be the number of vertices and edges of $G$. Onewell-known inequality is that $\mathcal{E}G\leq\lambda 1+\sqrt{n-12m-\lambda 1}$, where $\lambda 1$ is the spectralradius. If $G$ is $k$-regular, we have $\mathcal{E}G\leqk+\sqrt{kn-1n-k}$. Denote $\mathcal{E} 0=k+\sqrt{kn-1n-k}$.Balakrishnan {\it Linear Algebra Appl.} {\bf 387} 2004 287-295 proved thatfor each $\epsilon>0$, there exist infinitely many $n$ for each of which thereexists a $k$-regular graph $G$ of order $n$ with $k< n-1$ and$\frac{\mathcal{E}G}{\mathcal{E} 0}<\epsilon$, and proposed an open problemthat, given a positive integer $n\geq 3$, and $\epsilon>0$, does there exist a$k$-regular graph $G$ of order $n$ such that$\frac{\mathcal{E}G}{\mathcal{E} 0}>1-\epsilon$. In this paper, we show thatfor each $\epsilon>0$, there exist infinitely many such $n$ that$\frac{\mathcal{E}G}{\mathcal{E} 0}>1-\epsilon$. Moreover, we constructanother class of simpler graphs which also supports the first assertion that$\frac{\mathcal{E}G}{\mathcal{E} 0}<\epsilon$.



Author: Xueliang Li, Yiyang Li, Yongtang Shi

Source: https://arxiv.org/







Related documents