For a graph $G$ of order $n$, with adjacency eigenvalues $\lambda_1(G) \geq \cdots \geq \lambda_n(G)$, the \emph{energy} of $G$ is defined to be \[\mathcal{E}(G)=\sum_{i=1}^{n} |\lambda_i(G)|.\] A well-known conjecture from the 1980s by Fajtlowicz states that for any graph $G$, \[\mathcal{E}(G) \ge 2\left(n-\alpha(G)\right),\] where $\alpha(G)$ denotes the independence number. We prove this conjecture.
We prove that the energy ${\mathcal E}(G)$ of any simple graph $G$ of order $n\ge5$ satisfies \[ {\mathcal E}\ge r(G)+\bar d(G)-1, \] where $r(G)$ and $\bar d(G)$ denote, respectively, the rank of the adjacency matrix and the average degree of $G$. We also characterize all extremal graphs. As consequences, our result s...
Let $\gamma(G)$ denote the number of cliques in a graph $G$ and let $\Gamma(n):= \{\gamma(G):|V(G)|=n\}$ be the set of values of $\gamma(G)$ that can be attained on $n$ vertices. We improve on a result by Erd\H{o}s and Ern\'e to show that $| \Gamma(n)| \geq 2^{n-4\ln(2)\log^3(n)}$ for sufficiently large $n$.
Mihir Neve, Alexey Pokrovskiy, A. Shapiro· 0 citations
Let $\lambda_1(G) \geq \dots \geq \lambda_n(G)$ be the adjacency spectrum of a graph $G$ on $n$ vertices. The spectral distance $\sigma(G,H)$ between $n$-vertex graphs $G$ and $H$ is the Manhattan distance between their spectra, i.e. $\sigma(G,H) = \sum_{i=1}^n |\lambda_i(G) - \lambda_i(H)|$. Given a set $\mathcal{G}$...
Irena M. Jovanović, Jelena Sedlar, R. Škrekovski· 0 citations
Let $G$ be a graph of order $n$ with the adjacency eigenvalues $\lambda_1(G) \geq \dots \geq \lambda_n(G) $. Let $c(v)$ denote the maximum order of a clique containing vertex $v$. We prove the vertex-localized positive square-energy inequality \[ \sqrt{s_+(G)} \leq \sum_{v\in V}\left(1-\frac1{c(v)}\right), \] where \[...
Abhay Jayarajan, M. Kannan, Shivaramakrishna Pragada et al.· 0 citations
Let $G_{n,d}$ be a uniformly random simple $d$-regular graph on $n$ vertices, and let $A_n$ be its adjacency matrix. For every fixed $\lambda\in(0,1/2)$, we prove that for any $\lambda(n-1)\le d\le(1-\lambda)(n-1)$, $\mathbb P(A_n\text{ is singular})\le e^{-cn}$, where $c>0$ depends only on $\lambda$, and $n$ is suffic...
Ze-Yan Song, Han-Chao Wang, Sheng-Yan Yin et al.· 0 citations
Let $G$ be a connected graph, and let $\lambda_1(G)>\lambda_2(G)$ denote its two largest adjacency eigenvalues. The spectral gap of $G$ is defined as the difference $\lambda_1(G) - \lambda_2(G)$. For integers $r\geq 2$ and $s\geq 0$, the double kite $DK(r,s)$ is formed by taking two vertex-disjoint copies of the comple...
Le-Le Liu, Michael Tait, Yi Wang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
