2026-04-17T12:39:41Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/1004742026-01-30T01:56:11Zcom_2072_1033col_2072_452950

urn:hdl:2117/100474 The spectral excess theorem for distance-regular graphs having distance-d graph with fewer distinct eigenvalues Fiol Mora, Miquel Àngel Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria Graph theory Combinatorial analysis Distance-regular graph Kneser graph Partial antipodality Spectrum Predistance polynomials Polynomials Grafs, Teoria de Combinatòria Classificació AMS::05 Combinatorics::05C Graph theory Classificació AMS::05 Combinatorics::05E Algebraic combinatorics The final publication is available at Springer via http://dx.doi.org/10.1007/s10801-015-0654-6 Let Gamma be a distance-regular graph with diameter d and Kneser graph K = Gamma(d), the distance-d graph of Gamma. We say that Gamma is partially antipodal when K has fewer distinct eigenvalues than Gamma. In particular, this is the case of antipodal distance-regular graphs (K with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (K with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with d + 1 distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular. Peer Reviewed Postprint (author's final draft) 2016-06-01 Article http://link.springer.com/article/10.1007%2Fs10801-015-0654-6 info:eu-repo/grantAgreement/MICINN//MTM2011-28800-C02-01/ES/OPTIMIZACION Y PROBLEMAS EXTREMALES EN TEORIA DE GRAFOS Y COMBINATORIA. APLICACIONES A LAS REDES DE COMUNICACION./ info:eu-repo/grantAgreement/MINECO//MTM2014-60127-P/ES/TECNICAS DE OPTIMIZACION EN TEORIA DE GRAFOS, GRUPOS Y COMBINATORIA. APLICACIONES A REDES, ALGORITMOS Y PROTOCOLOS DE COMUNICACION./ http://creativecommons.org/licenses/by-nc-nd/3.0/es/ Open Access