To access the full text documents, please follow this link: http://hdl.handle.net/2117/11111

On almost distance-regular graphs
Dalfó Simó, Cristina; Van Dam, Edwin; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest; Gorissen, Bram
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV
Distance-regular graphs are a key concept in Algebraic Combinatoricsand have given rise to several generalizations, such as associationschemes. Motivated by spectral and other algebraic characterizationsof distance-regular 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 distance-regular graphis the invariance of the number of walks of given length betweenvertices at a given distance, while a graph is called walk-regular 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 distance-regularity and walk-regularity called m-walkregularity.Another studied concept is that of m-partial distanceregularityor, informally, distance-regularity up to distance m. Usingeigenvalues of graphs and the predistance polynomials, we discussand relate these and other concepts of almost distance-regularity,such as their common generalization of ( ,m)-walk-regularity. Weintroduce the concepts of punctual distance-regularity and punctualwalk-regularity 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 distance-regular becomes whole distance-regular. Wealso give several characterizations of punctually distance-regulargraphs that are generalizations of the spectral excess theorem.
2012-05-11
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
Graph theory
Distance-regular graph
Walk-regular graph
Eigenvalues
Local multiplicities
Predistance polynomial
Grafs, Teoria de
Restricted access - publisher's policy
Article
         

Show full item record

Related documents

Other documents of the same author

Dalfó Simó, Cristina; Van Dam, Edwin; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest; Gorissen, Bram
Dalfó Simó, Cristina; Van Dam, Edwin; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Dalfó Simó, Cristina; Van Dam, Edwin; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Dalfó Simó, Cristina; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Dalfó Simó, Cristina; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
 

Coordination

 

Supporters