Variants of spectral Turán theorems and eigenvectors of graphs

Abstract

In 2002, Nikiforov proved that for an $n$-vertex graph $G$ with clique number $\ddot{I}‰$ and edge number $m$, the spectral radius $\hat{I}»(G)$ satisfies $\hat{I}»(G)\le \sqrt{2(1-1/\ddot{I}‰)m}$, which confirmed a conjecture implicitly suggested by Edwards and Elphick. In this paper, we prove a local version of spectral Turán inequality, which states that $\hat{I}{»}^2(G)\le 2{\sum }_{e\in E(G)}\frac{c(e)-1}{c(e)}$, where $c(e)$ is the order of the largest clique containing the edge $e$ in $G$. We also characterize the extremal graphs. We prove that our theorem implies Nikiforov's theorem and give an example to show that the difference of Nikiforov's bound and ours is $\hat{I}\text{c◯}(\sqrt{m})$ for some cases. Additionally, we establish a spectral counterpart to Ore's problem (1962) which asks for the maximum size of an $n$-vertex graph such that its complement is connected and does not contain $F$ as a subgraph. Our result leads to a new spectral Turán inequality applicable to graphs with connected complements. Finally, we disprove a conjecture of Gregory, asserting that for a connected $n$-vertex graph $G$ with chromatic number $k\ge 2$ and an independent set $S$, we have \[ \sum_{v\in S} x_v^2 \leq \frac{1}{2} - \frac{k-2}{2\sqrt{(k-2)^2 + 4(k-1)(n-k+1)}}, \] where $x_v$ is the component of the Perron vector of $G$ with respect to the vertex $v$. A modified version of Gregory's conjecture is proposed.

20 pages. This is a new version of the previous paper titled "A local version of spectral Turán theorem". In this version, we add more results, including a variant of spectral Turán theorem and a disproof of a conjecture of Gregory