Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T01:46:27.901Z Has data issue: false hasContentIssue false

A classification of all 1-Salem graphs

Published online by Cambridge University Press:  01 November 2014

Lee Gumbrell
Affiliation:
Department of Mathematics, Royal Holloway, University of London, Egham Hill, Egham, Surrey, TW20 0EX, United Kingdom email Lee.Gumbrell@gmail.com
James McKee
Affiliation:
Department of Mathematics, Royal Holloway, University of London, Egham Hill, Egham, Surrey, TW20 0EX, United Kingdom email James.McKee@rhul.ac.uk

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
© The Author(s) 2014