An always nontrivial upper bound for Laplacian graph eigenvalues (Q1573668): Difference between revisions

Let \(G\) be a graph on \(n\) vertices \(v_1,\ldots,v_n\) with the adjacency matrix \(A\) and the diagonal matrix \(D\) of vertex degrees. The Laplacian matrix of \(G\) is defined by \(L=D-A\) and for its spectral radius \(\lambda_1\) holds the evident upper bound \(\lambda_1\leq n\). The main result of the paper under review is another upper bound for \(\lambda_1\) which does not exceed \(n\) for every \(G\): \(\lambda_1\leq\max\{d_i+d_j-|N_i\cap N_j|: 1\leq i<j\leq n\}\), where \(d_i\) denotes the degree of \(v_i\) and \(|N_i\cap N_j|\) is the number of common neighbours of \(v_i\) and \(v_j\).