{
  "id": "1109.6275",
  "version": "v2",
  "published": "2011-09-28T17:22:01.000Z",
  "updated": "2012-12-06T19:06:58.000Z",
  "title": "A classification of all 1-Salem graphs",
  "authors": [
    "Lee Gumbrell",
    "James McKee"
  ],
  "comment": "14 pages, 8 figures, 2 tables",
  "categories": [
    "math.CO"
  ],
  "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-trival Salem graphs)? Cyclotomic graphs were classified by Smith in 1970. 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: there are 26 infinite families and 383 sporadic examples.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-12-06T19:06:58.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "classification",
      "reciprocal polynomial",
      "cyclotomic graphs",
      "hand salem graphs",
      "spectrally close"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1109.6275G"
    }
  }
}