Edge distance-regular graphs
Autor: | Marc Cámara, Cristina Dalfó, E. Garriga, J. Fíbrega, Miguel Angel Fiol |
---|---|
Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada I, Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions |
Jazyk: | angličtina |
Rok vydání: | 2011 |
Předmět: |
Distance-regularity
Orthogonal polynomials Edge-distance-regular graph Distance-regular graph Theoretical Computer Science law.invention Combinatorics symbols.namesake law Graph power Generalized odd graph Line graph Predistance polynomials Discrete Mathematics and Combinatorics Adjacency matrix Complement graph Mathematics Discrete mathematics Grafs Teoria de Applied Mathematics Completely regular code Matemàtiques i estadística [Àrees temàtiques de la UPC] Polinomis ortogonals Planar graph Graph theory Graph energy Computational Theory and Mathematics Local spectra Spectral excess theorem symbols Regular graph |
Zdroj: | Recercat. Dipósit de la Recerca de Catalunya instname UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) Repositorio Abierto de la UdL Universitad de Lleida |
Popis: | Edge-distance-regularity is a concept recently introduced by the authors which is similar to that of distance-regularity, but now the graph is seen from each of its edges instead of from its vertices. More precisely, a graph Γ with adjacency matrix A is edge-distance-regular when it is distance-regular around each of its edges and with the same intersection numbers for any edge taken as a root. In this paper we study this concept, give some of its properties, such as the regularity of Γ, and derive some characterizations. In particular, it is shown that a graph is edge-distance-regular if and only if its k-incidence matrix is a polynomial of degree k in A multiplied by the (standard) incidence matrix. Also, the analogue of the spectral excess theorem for distance-regular graphs is proved, so giving a quasi-spectral characterization of edge-distance-regularity. Finally, it is shown that every nonbipartite graph which is both distance-regular and edge-distance-regular is a generalized odd graph. Supported by the Ministry of Science and Innovation of Spain under project MTM2008- 06620-C03-01 and by the Catalan Research Council under project 2009SGR01387 |
Databáze: | OpenAIRE |
Externí odkaz: |