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

When almost distance-regularity attains distance-regularity
Dalfó Simó, Cristina; Van Dam, Edwin; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV
Generally speaking, `almost distance-regular graphs' are graphs which share some, butnot necessarily all, regularity properties that characterize distance-regular graphs. Inthis paper we rst propose four basic di erent (but closely related) concepts of almostdistance-regularity. In some cases, they coincide with concepts introduced before byother authors, such as walk-regular graphs and partially distance-regular graphs. Hereit is always assumed that the diameter D of the graph attains its maximum possiblevalue allowed by its number d+1 of di erent eigenvalues; that is, D = d, as happens inevery distance-regular graph. Our study focuses on nding out when almost distance-regularity leads to distance-regularity. In other words, some `economic' (in the senseof 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 Astand 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 onthe preintersection parameters, the average intersection numbers and the recurrencecoe cients are obtained. In some cases, our results can be also seen as a generalizationof the so-called spectral excess theorem for distance-regular graphs.
2012-05-10
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
Graph theory
Eigenvalues
Grafs, Teoria de
Open Access
Conference Object
         

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; Gorissen, Bram
Dalfó Simó, Cristina; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
 

Coordination

 

Supporters