{
  "id": "1608.00091",
  "version": "v1",
  "published": "2016-07-30T08:27:45.000Z",
  "updated": "2016-07-30T08:27:45.000Z",
  "title": "Equivalent characterizations of the spectra of graphs and applications to measures of distance-regularity",
  "authors": [
    "V. Diego",
    "J. Fàbrega",
    "M. A. Fiol"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "As it is well known, the spectrum $ {\\rm sp\\,} \\Gamma$ (of the adjacency matrix $A$) of a graph $\\Gamma$, with $d$ distinct eigenvalues other than its spectral radius $\\lambda_0$, usually provides a lot of information about the structure of $G$. Moreover, from ${\\rm sp\\,}\\Gamma$ we can define the so-called predistance polynomials $p_0,\\ldots,p_d\\in {\\mathbb R}_d[x]$, with ${\\rm dgr\\,} p_i=i$, $i=0,\\ldots,d$, which are orthogonal with respect to the scalar product $\\langle f, g\\rangle_{\\Gamma} =\\frac{1}{n}{\\rm tr\\,}(f(A)g(A))$ and normalized in such a way that $\\|p_i\\|_{\\Gamma}^2=p_i(\\lambda_0)$. They can be seen as a generalization for any graph of the distance polynomials of a distance-regular graph. Going further, we consider the preintersection numbers $\\xi_{ij}^h$ for $i,j,h\\in\\{0,\\ldots,d\\}$, which generalize the intersection numbers of a distance-regular graph, and they are the Fourier coefficients of $p_ip_j$ in terms of the basis $\\{p_h\\}_{0\\le h\\le d}$. The aim of this paper is to show that, for any graph $\\Gamma$, the information contained in its spectrum, predistance polynomials, and preintersection numbers is equivalent. Also, we give some characterizations of distance-regularity which are based on the above concepts. For instance, we comment upon the so-called spectral excess theorem stating that a connected regular graph $G$ is distance-regular if and only if its spectral excess, which is the value of $p_d$ at $\\lambda_0$, equals the average excess, that is, the mean of the numbers of vertices at extremal distance $d$ from every vertex.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-07-30T08:27:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05E30",
      "05C50"
    ],
    "keywords": [
      "equivalent characterizations",
      "distance-regularity",
      "applications",
      "preintersection numbers",
      "distance-regular graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}