Bounds of eigenvalues of a nontrivial bipartite graph. (English) Zbl 1313.05230
Summary: Let \(G\) be a simple graph with \(n\) vertices and \(m\) edges, and let \(\lambda _1\) and \(\lambda _2\) denote the largest and second largest eigenvalues of \(G\). For a nontrivial bipartite graph \(G\), we prove that,
(i) \(\lambda _1\leq \sqrt {m-\frac {3-\sqrt {5}}{2}}\), where equality holds if and only if \(G\cong P_4\).
(ii) If \(G\ncong P_n\), then \(\lambda _1\leq \sqrt {m-\frac {5-\sqrt {17}}{2}}\), where equality holds if and only if \(G\cong K_{2,3}-e\).
(iii) If \(G\) is connected, then \(\lambda _2\leq \sqrt {m-4\cos ^2(\frac {\pi }{n+1})}\), where equality holds if and only if \(G\cong P_n\), \(2\leq n\leq 5\).
(iv) \(\lambda _2\geq \frac {\sqrt {5}-1}{2}\), where equality holds if and only if \(G\cong P_4\).
(v) If \(G\) is connected and \(G\ncong P_n\), then \(\lambda _2\geq \sqrt {\frac {5-\sqrt {17}}{2}}\), where equality holds if and only if \(G\cong K_{2,3}-e\).
(i) \(\lambda _1\leq \sqrt {m-\frac {3-\sqrt {5}}{2}}\), where equality holds if and only if \(G\cong P_4\).
(ii) If \(G\ncong P_n\), then \(\lambda _1\leq \sqrt {m-\frac {5-\sqrt {17}}{2}}\), where equality holds if and only if \(G\cong K_{2,3}-e\).
(iii) If \(G\) is connected, then \(\lambda _2\leq \sqrt {m-4\cos ^2(\frac {\pi }{n+1})}\), where equality holds if and only if \(G\cong P_n\), \(2\leq n\leq 5\).
(iv) \(\lambda _2\geq \frac {\sqrt {5}-1}{2}\), where equality holds if and only if \(G\cong P_4\).
(v) If \(G\) is connected and \(G\ncong P_n\), then \(\lambda _2\geq \sqrt {\frac {5-\sqrt {17}}{2}}\), where equality holds if and only if \(G\cong K_{2,3}-e\).
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
