EMIS ELibM Electronic Journals Bulletin, Classe des Sciences Mathématiques et Naturelles, Sciences mathématiques naturelles / sciences mathematiques
Vol. CXXXIII, No. 31, pp. 41–55 (2006)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home


Pick a mirror


Graphs with least eigenvalue $-2$ attaining a convex quadratic upper bound for the stability number

D. M. Cardoso and D. Cvetkovic

Department of Mathematics, University of Aveiro, 3810-193, Aveiro, Portugal, E-mail: dcardoso@mat.ua.pt
Faculty of Electrical Engineering, University of Belgrade, P.O.Box 35–54, 11120 Belgrade, Serbia, E-mail: ecvetkod@etf.bg.ac.yu

Abstract: In this paper 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.

Keywords: graph theory, graph spectra, line graph , quadratic programming, stability number

Classification (MSC2000): 05C50

Full text of the article: (for faster download, first choose a mirror)

Electronic fulltext finalized on: 10 Jun 2006. This page was last modified: 20 Jun 2011.

© 2006 Mathematical Institute of the Serbian Academy of Science and Arts
© 2006–2011 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition