On graphs whose second largest eigenvalue does not exceed \((\sqrt {5}-1)/2\) (Q1842163): Difference between revisions

Let \(\lambda_1, \lambda_2,\dots, \lambda_n\) be the list of eigenvalues of a graph \(G\), \(\lambda_1\geq \lambda_2\geq\cdots\geq \lambda_n\). The structure of graphs with \(\lambda_2= \lambda_2(G)\leq (\sqrt 5- 1)/2\) is studied. The problem was put in [\textit{D. Cao} and \textit{H. Yuan}, Graphs characterized by the second eigenvalue, J. Graph Theory 17, No. 3, 325-331 (1993; Zbl 0786.05055)], where the graphs with \(0< \lambda_2< 1/3\) were completely described. Put \((\sqrt 5- 1)/2= \sigma\). A graph \(G\) is called \(\sigma\)-graph if \(\lambda_2(G)\leq \sigma\). It is proved that every \(\sigma\)-graph has at most one nontrivial connected component. For a connected \(\sigma\)-graph \(G\) one of the following holds: (1) \(G\) is a complete multipartite graph, (2) \(G\) is an induced subgraph of \(C_5\), (3) \(G\) contains a triangle. In Case (3) a local description of \(\sigma\)-graphs is given. Namely, let \(T\) be a triangle in \(G\), and let \(A= A(T)\), \(B= B(T)\) and \(C= C(T)\) be the sets of vertices of \(G\) which do not belong to \(T\) and are adjacent to exactly one, two and three vertices of \(T\), respectively. Let \(G_A\) be the connected component of the graph \(G- B- C\) containing \(T\). The components \(G_B\) and \(G_C\) of the graphs \(G- A- C\) and \(G- A- B\), respectively, are defined similarly. The possible structure of \(G_A\), \(G_B\) and \(G_C\) is described. This profound result does not contain a complete description of \(\sigma\)-graphs, but allows reduction. The class of \(\sigma\)-graphs is hereditary and hence can be characterized by the list of forbidden induced subgraphs. It is announced that the list \(F\) of minimal forbidden induced subgraphs for this class is finite. A sketch of the proof and a part of \(F\) are given. A complete proof will appear in a subsequent paper of the authors.