A classification of all 1-Salem graphs. Issue Volume 17:Issue A(2014) (November 2014)

• Record Type: Journal Article
• Authors: Gumbrell, Lee; McKee, James
• Is Part Of: LMS journal of computation and mathematics. Volume 17:Issue A(2014)
• Page Start: 582
• Page End: 594
• Publication Date: 2014-11
• Subjects: 11R06, -- 05C50 (primary)
• DOI: 10.1112/S1461157014000060
• Languages: English
• ISSNs: 1461-1570

Abstract

Abstract: 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_{G}$, and with two particular classes of reciprocal polynomials in mind one can ask the questions: (a) when is $R_{G}$ a product of cyclotomic polynomials (giving the cyclotomic graphs )? (b) when does $R_{G}$ have the minimal polynomial of a Salem number as its only non-cyclotomic factor (the non-trivial Salem graphs )? Cyclotomic graphs were classified by Smith ( Combinatorial structures and their applications, Proceedings of Calgary International Conference, Calgary, AB, 1969 (eds R. Guy, H. Hanani, H. Saver and J. Schönheim; Gordon and Breach, New York, 1970) 403–406); 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$ infinite families and $383$ sporadic examples.