Eigenvalues and extremal degrees of graphs (Q865434): Difference between revisions

Let \(G\) be a graph on \(\{1,2,\dots,n\},\) \(d_i\) the degree of node \(i\) of \(G,\) \(D(G)=\text{diag}(d_1,\dots, d_n),\) \(\delta(G)=\min_i d_i,\) \(\Delta(G)=\max_i d_i,\) \(A(G)\) the adjacency matrix of \(G,\) \(\mu_1(G)\geq \cdots \geq \mu_n(G)\) its eigenvalues, \(L(G)=D(G)-A(G)\) its Laplacian, and \(\lambda_1(G) \leq \cdots \leq \lambda_n(G)\) the eigenvalues of \(L(G)\). Denote by \(\overline{G}\) the complement of graph \(G.\) \quad Using the variational characterization of the eigenvalues of Hermitian matrices it is shown that \( \delta(G)\leq \mu_k(G)+\lambda_k(G) \leq \Delta(G),\) implying \(\mu_k(G)+\mu_{n-k+2}(\overline{G}) \geq \delta(G)-\Delta(G)-1, \) \(k=(1),2,\dots,n.\) In \textit{F. R. K. Chung, R. L. Graham} and \textit{R. M. Wilson} [Combinatorica 9, 345-362 (1989; Zbl 0715.05057)] an infinite family \({\mathcal G}\) of graphs was defined to be quasi-random if, as \(G\) ranges over the graphs of order \(n\) of \({\mathcal G},\) we have \(\mu_1(G)=2 e(G)/n+o(n),\) \(\mu_2(G)=o(n),\) and \(\mu_n(G)=o(n).\) It is shown that \(\mu_n(G)+\mu_n(\overline{G})=o(n)\) is necessary and sufficient for quasi-randomness of \({\mathcal G},\) while either of the properties \(\lambda_n(G)+\lambda_n(\overline{G})=n+o(n)\) or \(\lambda_2(G)+\lambda_2(\overline{G})=o(n)\) is a sufficient condition for quasi-randomness.