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

Research output: Contribution to journal › Article

Published

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

Research output: Contribution to journal › Article

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

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

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

@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",

}

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 -