Cardoso, D. M.; Cvetković, D. Graphs with least eigenvalue \(-2\) attaining a convex quadratic upper bound for the stability number. (English) Zbl 1265.05353 Bull., Cl. Sci. Math. Nat., Sci. Math. 133, No. 31, 41-55 (2006). Authors’ abstract: We study the conditions under which the stability number of line graphs, generalized line graphs and exceptional graphs attains a convex quadratic programming upper bound. In regular graphs this bound is reduced to the well known Hoffman bound. Some vertex subsets inducing subgraphs with regularity properties are analyzed. Based on an observation concerning the Hoffman bound a new construction of regular exceptional graphs is provided. Reviewer: Slobodan Simić (Beograd) Cited in 11 Documents MSC: 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C76 Graph operations (line graphs, products, etc.) 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 90C20 Quadratic programming Keywords:line graph; convex quadratic programming upper bound; Hoffman bound; generalized line graphs; regular exceptional graphs PDFBibTeX XMLCite \textit{D. M. Cardoso} and \textit{D. Cvetković}, Bull., Cl. Sci. Math. Nat., Sci. Math. 133, No. 31, 41--55 (2006; Zbl 1265.05353) Full Text: DOI