×

Revisiting two classical results on graph spectra. (English) Zbl 1111.05062

Summary: Let \(\mu(G)\) and \(\mu_{\min}(G)\) 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(G) -\mu(H) > 1/(\mu(G)^{2D}n)\), and (ii) if \(G\) is a connected nonbipartite graph of order \(n\) and diameter \(D\), then \(\mu(G) +\mu_{\min}(G) > 2/(\mu(G)^{2D}n).\) For large \(\mu\) and \(D\) these bounds are close to the best possible ones.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: arXiv EuDML EMIS