Abstract:

Distanceregular graphs are a key concept in Algebraic Combinatoricsand have given rise to several generalizations, such as associationschemes. Motivated by spectral and other algebraic characterizationsof distanceregular graphs, we study ‘almost distanceregulargraphs’. We use this name informally for graphs that sharesome regularity properties that are related to distance in the graph.For example, a known characterization of a distanceregular graphis the invariance of the number of walks of given length betweenvertices at a given distance, while a graph is called walkregular ifthe number of closed walks of given length rooted at any given vertexis a constant. One of the concepts studied here is a generalizationof both distanceregularity and walkregularity called mwalkregularity.Another studied concept is that of mpartial distanceregularityor, informally, distanceregularity up to distance m. Usingeigenvalues of graphs and the predistance polynomials, we discussand relate these and other concepts of almost distanceregularity,such as their common generalization of ( ,m)walkregularity. Weintroduce the concepts of punctual distanceregularity and punctualwalkregularity as a fundament upon which almost distanceregulargraphs are built. We provide examples that are mostlytaken from the Foster census, a collection of symmetric cubicgraphs. Two problems are posed that are related to the question ofwhen almost distanceregular becomes whole distanceregular. Wealso give several characterizations of punctually distanceregulargraphs that are generalizations of the spectral excess theorem. 