A classification of all 1-Salem graphs. / McKee, James; Gumbrell, Lee.

In: LMS Journal of Computation and Mathematics, Vol. 17, No. 1, 2014, p. 582-594.

Research output: Contribution to journalArticle

Published

Standard

A classification of all 1-Salem graphs. / McKee, James; Gumbrell, Lee.

In: LMS Journal of Computation and Mathematics, Vol. 17, No. 1, 2014, p. 582-594.

Research output: Contribution to journalArticle

Harvard

McKee, J & Gumbrell, L 2014, 'A classification of all 1-Salem graphs', LMS Journal of Computation and Mathematics, vol. 17, no. 1, pp. 582-594. https://doi.org/10.1112/S1461157014000060

APA

McKee, J., & Gumbrell, L. (2014). A classification of all 1-Salem graphs. LMS Journal of Computation and Mathematics, 17(1), 582-594. https://doi.org/10.1112/S1461157014000060

Vancouver

McKee J, Gumbrell L. A classification of all 1-Salem graphs. LMS Journal of Computation and Mathematics. 2014;17(1):582-594. https://doi.org/10.1112/S1461157014000060

Author

McKee, James ; Gumbrell, Lee. / A classification of all 1-Salem graphs. In: LMS Journal of Computation and Mathematics. 2014 ; Vol. 17, No. 1. pp. 582-594.

BibTeX

@article{4e75e3ff66c14b52b0116118ff2b5700,
title = "A classification of all 1-Salem graphs",
abstract = "One way to study certain classes of polynomials is by consideringexamples that are attached to combinatorial objects. Any graph G has an associatedreciprocal polynomial R, and with two particular classes of reciprocalpolynomials in mind one can ask the questions: (a) when is R a product of cyclotomicpolynomials (giving the cyclotomic graphs)? (b) when does R havethe minimal polynomial of a Salem number as its only non-cyclotomic factor(the non-trival Salem graphs)? Cyclotomic graphs were classied by Smith in1970; the maximal connected ones are known as Smith graphs. Salem graphsare `spectrally close' to being cyclotomic, in that nearly all their eigenvaluesare in the critical interval [-2; 2]. On the other hand Salem graphs do notneed to be `combinatorially close' to being cyclotomic: the largest cyclotomicinduced subgraph might be comparatively tiny.We define an m-Salem graph to be a connected Salem graph G for whichm is minimal such that there exists an induced cyclotomic subgraph of G thathas m fewer vertices than G. The 1-Salem subgraphs are both spectrally closeand combinatorially close to being cyclotomic. Moreover, every Salem graphcontains a 1-Salem graph as an induced subgraph, so these 1-Salem graphsprovide some necessary substructure of all Salem graphs. The main result ofthis paper is a complete combinatorial description of all 1-Salem graphs: inthe non-bipartite case there are 25 innite families and 383 sporadic examples.",
author = "James McKee and Lee Gumbrell",
year = "2014",
doi = "http://dx.doi.org/10.1112/S1461157014000060",
language = "English",
volume = "17",
pages = "582--594",
journal = "LMS Journal of Computation and Mathematics",
issn = "1461-1570",
publisher = "Cambridge University Press",
number = "1",

}

RIS

TY - JOUR

T1 - A classification of all 1-Salem graphs

AU - McKee, James

AU - Gumbrell, Lee

PY - 2014

Y1 - 2014

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

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

U2 - http://dx.doi.org/10.1112/S1461157014000060

DO - http://dx.doi.org/10.1112/S1461157014000060

M3 - Article

VL - 17

SP - 582

EP - 594

JO - LMS Journal of Computation and Mathematics

JF - LMS Journal of Computation and Mathematics

SN - 1461-1570

IS - 1

ER -