Dual concepts of almost distance-regularity and the spectral excess theorem
| Autor: | Miguel Angel Fiol, E.R. van Dam, E. Garriga, Cristina Dalfó |
|---|---|
| Přispěvatelé: | Research Group: Operations Research, Econometrics and Operations Research |
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
ComputingMilieux_LEGALASPECTSOFCOMPUTING
Theoretical Computer Science Combinatorics Indifference graph Pathwidth distance-regular graph Chordal graph local spectrum FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics distance matrices Mathematics Discrete mathematics Clique-sum predistance polynomials Grafs Teoria de Strong perfect graph theorem Eigenvalues Spectrum analysis Modular decomposition Graph theory Anàlisi espectral Valors propis idempotents Maximal independent set Combinatorics (math.CO) 05E30 05C50 05 Combinatorics::05C Graph theory [Classificació AMS] Graph product Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC] |
| Zdroj: | UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) Discrete Mathematics, 312(17), 2730-2734. Elsevier |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2012.03.003 |
| Popis: | Generally speaking, ‘almost distance-regular’ graphs are graphs that share some, but not necessarily all, regularity properties that characterize distance-regular graphs. In this paper we first propose two dual concepts of almost distance-regularity. In some cases, they coincide with concepts introduced before by other authors, such as partially distance-regular graphs. Our study focuses on finding out when almost distance-regularity leads to distance-regularity. In particular, some ‘economic’ (in the sense of minimizing the number of conditions) old and new characterizations of distance-regularity are discussed. Moreover, other characterizations based on the average intersection numbers and the recurrence coefficients are obtained. In some cases, our results can also be seen as a generalization of the so-called spectral excess theorem for distance-regular graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect