Distance-regular graphs are a key concept in Algebraic Combinatorics
and have given rise to several generalizations, such as association
schemes. Motivated by spectral and other algebraic characterizations
of distance-regular graphs, we study ‘almost distanceregular
graphs’. We use this name informally for graphs that share
some regularity properties that are related to distance in the graph.
For example, a known characterization of a distance-regular graph
is the invariance of the number of...
Distance-regular graphs are a key concept in Algebraic Combinatorics
and have given rise to several generalizations, such as association
schemes. Motivated by spectral and other algebraic characterizations
of distance-regular graphs, we study ‘almost distanceregular
graphs’. We use this name informally for graphs that share
some regularity properties that are related to distance in the graph.
For example, a known characterization of a distance-regular graph
is the invariance of the number of walks of given length between
vertices at a given distance, while a graph is called walk-regular if
the number of closed walks of given length rooted at any given vertex
is a constant. One of the concepts studied here is a generalization
of both distance-regularity and walk-regularity called m-walkregularity.
Another studied concept is that of m-partial distanceregularity
or, informally, distance-regularity up to distance m. Using
eigenvalues of graphs and the predistance polynomials, we discuss
and relate these and other concepts of almost distance-regularity,
such as their common generalization of ( ,m)-walk-regularity. We
introduce the concepts of punctual distance-regularity and punctual
walk-regularity as a fundament upon which almost distanceregular
graphs are built. We provide examples that are mostly
taken from the Foster census, a collection of symmetric cubic
graphs. Two problems are posed that are related to the question of
when almost distance-regular becomes whole distance-regular. We
also give several characterizations of punctually distance-regular
graphs that are generalizations of the spectral excess theorem.
Citation
Dalfo, C. [et al.]. On almost distance-regular graphs. "Journal of combinatorial theory. Series A", 2010.