A classification of all 1-Salem graphs

One way to study certain classes of polynomials is by considering
examples that are attached to combinatorial objects. Any graph G has an associated
reciprocal polynomial R, and with two particular classes of reciprocal
polynomials in mind one can ask the questions: (a) when is R a product of cyclotomic
polynomials (giving the cyclotomic graphs)? (b) when does R have
the minimal polynomial of a Salem number as its only non-cyclotomic factor
(the non-trival Salem graphs)? Cyclotomic graphs were classied by Smith in
1970; the maximal connected ones are known as Smith graphs. Salem graphs
are `spectrally close' to being cyclotomic, in that nearly all their eigenvalues
are in the critical interval [-2; 2]. On the other hand Salem graphs do not
need to be `combinatorially close' to being cyclotomic: the largest cyclotomic
induced subgraph might be comparatively tiny.
We define an m-Salem graph to be a connected Salem graph G for which
m is minimal such that there exists an induced cyclotomic subgraph of G that
has m fewer vertices than G. The 1-Salem subgraphs are both spectrally close
and combinatorially close to being cyclotomic. Moreover, every Salem graph
contains a 1-Salem graph as an induced subgraph, so these 1-Salem graphs
provide some necessary substructure of all Salem graphs. The main result of
this paper is a complete combinatorial description of all 1-Salem graphs: in
the non-bipartite case there are 25 innite families and 383 sporadic examples.