Generally speaking, `almost distance-regular graphs' are graphs which share some, but
not necessarily all, regularity properties that characterize distance-regular graphs. In
this paper we rst propose four basic di erent (but closely related) concepts of almost
distance-regularity. In some cases, they coincide with concepts introduced before by
other authors, such as walk-regular graphs and partially distance-regular graphs. Here
it is always assumed that the diameter D of the graph attains its...
Generally speaking, `almost distance-regular graphs' are graphs which share some, but
not necessarily all, regularity properties that characterize distance-regular graphs. In
this paper we rst propose four basic di erent (but closely related) concepts of almost
distance-regularity. In some cases, they coincide with concepts introduced before by
other authors, such as walk-regular graphs and partially distance-regular graphs. Here
it is always assumed that the diameter D of the graph attains its maximum possible
value allowed by its number d+1 of di erent eigenvalues; that is, D = d, as happens in
every distance-regular graph. Our study focuses on nding out when almost distance-
regularity leads to distance-regularity. In other words, some `economic' (in the sense
of minimizing the number of conditions) old and new characterizations of distance-
regularity are discussed. For instance, if A0;A1; : : : ;AD and E0;E1; : : : ;Ed denote,
respectively, the distance matrices and the idempotents of the graph; and D and A
stand for their respective linear spans, any of the two following `dual' conditions su ce:
(a) A0;A1;AD 2 A; (b) E0;E1;Ed 2 D. Moreover, other characterizations based on
the preintersection parameters, the average intersection numbers and the recurrence
coe cients are obtained. In some cases, our results can be also seen as a generalization
of the so-called spectral excess theorem for distance-regular graphs.
Citation
Dalfo, C. [et al.]. When almost distance-regularity attains distance-regularity. A: 8th French Combinatorial Conference. "8th French Combinatorial Conference". Orsay, París: 2010, p. 99.