2012

A short proof of the odd-girth theorem

van Dam, Edwin R., Fiol, Miquel Angel

Understand

Recently, it has been shown that a connected graph $\Gamma$ with $d+1$ distinct eigenvalues and odd-girth $2d+1$ is distance-regular.

  • The proof of this result was based on the spectral excess theorem.
  • In this note we present an alternative and more direct proof which does not rely on the spectral excess theorem, but on a known characterization of distance-regular graphs in terms of the predistance polynomial of degree $d$.

Built on

  • C.D. Godsil and B.D. McKay, Feasibility conditions for the existence of walk-regular graphs,

    1980

    Earlier work this paper cites.

  • D. M. Cvetković, M. Doob, and H. Sachs,

    1982

    Earlier work this paper cites.

  • A.E. Brouwer, A.M. Cohen, and A. Neumaier,

    1989

    Earlier work this paper cites.

  • N. Biggs,

    1993

    Earlier work this paper cites.

  • M.A. Fiol, E. Garriga, and J.L.A. Yebra, Locally pseudo-distance-regular graphs,

    1996

    Earlier work this paper cites.

Similar

  • M.A. Fiol and E. Garriga, From local adjacency polynomials to locally pseudo-distance-regular graphs,

    1997

    Cited alongside, same era.

  • T. Huang and C. Liu, Spectral characterization of some generalized odd graphs

    1999

    Cited alongside, same era.

  • M.A. Fiol, Algebraic characterizations of distance-regular graphs,

    2002

    Cited alongside, same era.

  • E.R. van Dam, The spectral excess theorem for distance-regular graphs: a global (over)view,

    2008

    Cited alongside, same era.

  • M.A. Fiol, S. Gago, and E. Garriga, A simple proof of the spectral excess theorem for distance-regular graphs,

    2010

    Cited alongside, same era.

Then

  • E.R. van Dam and W.H. Haemers, An odd characterization of the generalized odd graphs,

    2011

    Later among the works it cites.

  • A.E. Brouwer and W.H. Haemers,

    2012

    Closest in time.

  • E.R. van Dam, J.H. Koolen, and H. Tanaka, Distance-regular graphs, manuscript (2012), available online at

    2012

    Closest in time.

  • G.-S. Lee and C.-w. Weng, The spectral excess theorem for general graphs,

    2012

    Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…