A recursive construction of the regular exceptional graphs with least eigenvalue –2

  • Inês Barbedo

    Politechnic Institute of Bragança, Mirandela, Portugal
  • Domingos M. Cardoso

    Universidade de Aveiro, Portugal
  • Dragoš Cvetković

    Serbian Academy of Sciences and Arts, Belgrade, Serbia
  • Paula Rama

    Universidade de Aveiro, Portugal
  • Slobodan K. Simić

    Serbian Academy of Sciences and Arts, Belgrade, Serbia

Abstract

In spectral graph theory a graph with least eigenvalue is exceptional if it is connected, has least eigenvalue greater than or equal to , and it is not a generalized line graph. A -regular set of a graph is a vertex subset, inducing a -regular subgraph such that every vertex not in has neighbors in . We present a recursive construction of all regular exceptional graphs as successive extensions by regular sets.

Cite this article

Inês Barbedo, Domingos M. Cardoso, Dragoš Cvetković, Paula Rama, Slobodan K. Simić, A recursive construction of the regular exceptional graphs with least eigenvalue –2. Port. Math. 71 (2014), no. 2, pp. 79–96

DOI 10.4171/PM/1942