Revisiting Two Classical Results on Graph Spectra

Vladimir Nikiforov

Abstract


Let $\mu\left( G\right) $ and $\mu_{\min}\left( G\right) $ be the largest and smallest eigenvalues of the adjacency matrix of a graph $G$. Our main results are:

(i) If $H$ is a proper subgraph of a connected graph $G$ of order $n$ and diameter $D$, then $$ \mu\left( G\right) -\mu\left( H\right) >{1\over\mu\left( G\right) ^{2D}n}. $$

(ii) If $G$ is a connected nonbipartite graph of order $n$ and diameter $D$, then $$ \mu\left( G\right) +\mu_{\min}\left( G\right) >{2\over\mu\left( G\right) ^{2D}n}. $$ For large $\mu $ and $D$ these bounds are close to the best possible ones.


Full Text: PDF