The spread of the spectrum of a graph (Q5946174): Difference between revisions

Let \(A=A(G)\) be the adjacency matrix of a simple graph \(G\) with \(n\) vertices and \(e\) edges, and let \(\lambda_1\geq\lambda_2\geq\dots\geq\lambda_n\) be its eigenvalues. The spread \(s(G)\) is the difference \(\lambda_1-\lambda_n\). The authors consider the maximum spread of graphs under various constraints. Let \(G_0\) denote the subgraph of \(G\) obtained by deleting the isolated vertices of \(G\). The main result is the following Theorem 2.3: Let \(G\) be a graph with \(n\) vertices, \(e\) edges, and precisely \(k\) negative eigenvalues, \(1\leq k\leq n-1\). Then \[ s(G) \leq \frac{k+1}k \lambda_1 + \sqrt{ 2e \frac{k-1}k - \frac{k^2-1}{k^2} \lambda_1^2}. \] Equality holds if and only if \(G_0\) is a complete \((k+1)\)-partite graph and, when \(k\geq 3\), the \(k\) smallest parts of \(G_0\) all have equal size. The authors also find a number of other upper bounds on the spread of a graph with constant number of edges under some additional conditions. Next, the authors consider a conjecture about the maximum spread amongst the graphs with \(n\) vertices. The join of two vertex disjoint graphs \(G_1\) and \(G_2\) is the graph \(G_1\vee G_2\) obtained from their union by including all edges between the vertices in \(G_1\) and the vertices in \(G_2\). For integers \(1\leq k\leq n-1\), let \(G(n,k)=K_k\vee \overline K_{n-k}\), the join of \(K_k\), the complete graph with \(k\) vertices, with the \(n-k\) independent vertices of \(\overline K_{n-k}\), the complement of \(K_{n-k}\). The graph \(G(n,\lceil 2n/3\rceil)\) has the spread \(s(G(n,\lceil 2n/3\rceil)) = \lceil (4/3)(n^2-n+1)\rceil^{1/2}\) and so \((1/\sqrt 3)(2n-1) < s(G(n,\lceil 2n/3\rceil)) < (1/\sqrt 3)(2n-1) + {\sqrt 3}/(4n-2)\) (or \(s(G(n,\lceil 2n/3\rceil)) \approx 1.1547n-0.5774\)). The authors conjecture that the maximum spread \(s(n)\) amongst the graphs with \(n\) vertices is attained only by \(G(n,\lceil 2n/3\rceil)\). This conjecture has been checked by computer for graphs with at most \(9\) vertices and it is supported by the upper bound \(s(n)\leq (1/2)(1+\sqrt 2)n\) (or \(s(n) < 1.2072n\)) the authors prove. Among other results the authors prove that a triangle-free graph with \(n\) vertices, \(e\) edges, and maximum vertex degree \(k\) has a spread at least \((2e/n)+\sqrt k\). This minimum spread is attained by Johnson graphs \(J(2r,r)\), for example.