Tree-width, clique-minors, and eigenvalues. (Q1421528): Difference between revisions

Let \(G\) be a simple graph of order \(n\). Let \(\rho(G)\) be the spectral radius of \(G\) and let \(\lambda(G)\) be the least eigenvalue of \(G\). The author proves the following results: If \(G\) is \(K_5\) minor-free graph, then \(\rho(G) \leq 1 + \sqrt{3n - 8}\), where equality holds if and only if \(G\) is isomorphic to \(K_3 \nabla (n-3)K_1\); and if \(G\) is \(K_5\) minor-free graph with \(n\geq 5\) vertices, then \(\lambda(G) \geq -\sqrt{3n - 9}\), where equality holds if and only if \(G\) is isomorphic to \(K_{3,n-3}\).