On almost distance-regular graphs

DOI10.1016/J.JCTA.2010.10.005zbMATH Open1225.05249arXiv1202.3265OpenAlexW2167900279MaRDI QIDQ2431269FDOQ2431269

Authors: C. Dalfó, E. Garriga, Bram L. Gorissen, Edwin R. Van Dam, Miquel Angel Fiol 

Publication date: 11 April 2011

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Distance-regular graphs are a key concept in Algebraic Combinatorics and have given rise to several generalizations, such as association schemes. Motivated by spectral and other algebraic characterizations of distance-regular graphs, we study `almost distance-regular graphs'. We use this name informally for graphs that share some regularity properties that are related to distance in the graph. For example, a known characterization of a distance-regular graph is the invariance of the number of walks of given length between vertices at a given distance, while a graph is called walk-regular if the number of closed walks of given length rooted at any given vertex is a constant. One of the concepts studied here is a generalization of both distance-regularity and walk-regularity called $m$-walk-regularity. Another studied concept is that of $m$-partial distance-regularity or, informally, distance-regularity up to distance $m$. Using eigenvalues of graphs and the predistance polynomials, we discuss and relate these and other concepts of almost distance-regularity, such as their common generalization of $(ell,m)$-walk-regularity. We introduce the concepts of punctual distance-regularity and punctual walk-regularity as a fundament upon which almost distance-regular graphs are built. We provide examples that are mostly taken from the Foster census, a collection of symmetric cubic graphs. Two problems are posed that are related to the question of when almost distance-regular becomes whole distance-regular. We also give several characterizations of punctually distance-regular graphs that are generalizations of the spectral excess theorem.

Full work available at URL: https://arxiv.org/abs/1202.3265

Recommendations

• Dual concepts of almost distance-regularity and the spectral excess theorem
• On perturbations of almost distance-regular graphs
• Algebraic characterizations of distance-regular graphs
• scientific article; zbMATH DE number 4108821
• Distance-regular graphs

zbMATH Keywords

eigenvaluesdistance-regular graphpredistance polynomialwalk-regular graphlocal multiplicities

Mathematics Subject Classification ID

Association schemes, strongly regular graphs (05E30) Distance in graphs (05C12)

Cites Work

• Title not available (Why is that?)
• Algebraic Graph Theory
• The spectral excess theorem for distance-regular graphs: a global (over)view
• Locally pseudo-distance-regular graphs
• Problems in algebraic combinatorics
• From local adjacency polynomials to locally pseudo-distance-regular graphs
• On the Polynomial of a Graph
• Characterizing distance-regularity of graphs by the spectrum
• Title not available (Why is that?)
• Feasibility conditions for the existence of walk-regular graphs
• On distance-regularity in graphs
• Algebraic characterizations of distance-regular graphs
• On the algebraic theory of pseudo-distance-regularity around a set
• A simple proof of the spectral excess theorem for distance-regular graphs
• Characterizing \((\ell ,m)\)-walk-regular graphs
• Higmanian rank-5 association schemes on 40 points
• Boundary graphs: The limit case of a spectral property
• On \(k\)-walk-regular graphs
• Title not available (Why is that?)
• Commutative association schemes
• The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs
• Title not available (Why is that?)
• Distance degree regular graphs
• Title not available (Why is that?)
• Vertex-symmetric generalized Moore graphs.

Cited In (49)

• A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
• Edge-distance-regular graphs are distance-regular
• The spectral excess theorem for distance-regular graphs having distance-\(d\) graph with fewer distinct eigenvalues
• Spectrally extremal vertices, strong cospectrality, and state transfer
• Algebraic characterizations of regularity properties in bipartite graphs
• A spectral excess theorem for nonregular graphs
• Dual concepts of almost distance-regularity and the spectral excess theorem
• Geometric aspects of 2-walk-regular graphs
• Algebraic characterizations of distance-regular graphs
• On perturbations of almost distance-regular graphs
• On the non-existence of antipodal cages of even girth
• Partially metric association schemes with a multiplicity three
• Two results concerning distance-regular directed graphs
• Distance regular graphs arising from dimensional dual hyperovals
• 2-walk-regular dihedrants from group-divisible designs
• Title not available (Why is that?)
• A spectral equivalent condition of the \(P\)-polynomial property for association schemes
• Some spectral and quasi-spectral characterizations of distance-regular graphs
• Kite-free distance-regular graphs
• Distance regularity in direct-product graphs
• Title not available (Why is that?)
• Pseudo 1-homogeneous distance-regular graphs
• Distance-regular graphs and \((\alpha,\beta)\)-geometries
• Resistance characterizations of equiarboreal graphs
• Distance-regular graphs with strongly regular subconstituents
• Quotient-polynomial graphs
• The distance-regular graphs with valency \(k \geq 2\), diameter \(D \geq 3\) and \(k_{D - 1} + k_D \leq 2 k\)
• Equivalent characterizations of the spectra of graphs and applications to measures of distance-regularity
• Edge-disjoint spanning trees and forests of graphs
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• The 2-partially distance-regular graphs such that their second largest local eigenvalues are at most one
• On bipartite distance-regular Cayley graphs with small diameter
• 2-walk-regular graphs with a small number of vertices compared to the valency
• On symmetric association schemes and associated quotient-polynomial graphs
• Some elementary inequalities for distance-regular graphs
• A characterization of bipartite distance-regular graphs
• Retracing argument for distance-regular graphs
• Some results on the eigenvalues of distance-regular graphs
• On 2-walk-regular graphs with a large intersection number \(c_2\)
• On bipartite cages of excess 4
• The spectral excess theorem for graphs with few eigenvalues whose distance-2 or distance-1-or-2 graph is strongly regular
• Title not available (Why is that?)
• A spectral excess theorem for digraphs with normal Laplacian matrices
• On some approaches to the spectral excess theorem for nonregular graphs
• The spectral excess theorem for distance-biregular graphs.
• Thin \(Q\)-polynomial distance-regular graphs have bounded \(c_2\)
• A spectral excess theorem for normal digraphs
• 2-reconstructibility of strongly regular graphs and 2-partially distance-regular graphs
• Edge-distance-regular graphs

This page was built for publication: On almost distance-regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431269)