## 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, 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.

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.

Original language | English |
---|---|

Pages (from-to) | 582-594 |

Number of pages | 13 |

Journal | LMS Journal of Computation and Mathematics |

Volume | 17 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2014 |