The largest eigenvalue of nonregular graphs (Q1826960): Difference between revisions

Consider a connected simple graph \(G=(V, E)\) with \(n=| V| \geq 2\) vertices, a set of branches \(E\), and an adjacency matrix \(A\). Denote \(d_i\), \(i\in V\), the degree of vertex \(i\) with \(\Delta =\,\,\)max\(_i\,\, d_i\) and \(\lambda_1\) the largest eigenvalue of \(A\). If \(G\) is regular, i.e. \(d_i=\Delta\) for each \(i\), then \(\lambda_1=\Delta\). It is proved that if \(G\) is connected and non-regular, then \[ \lambda_1<\Delta-{1\over 2n(n\Delta -1)\Delta^2}. \]