On perturbations of almost distance-regular graphs

DOI10.1016/J.LAA.2011.05.004zbMATH Open1222.05152arXiv1202.3313OpenAlexW1981862027MaRDI QIDQ550646FDOQ550646

Authors: C. Dalfó, Edwin R. Van Dam, Miquel Angel Fiol 

Publication date: 13 July 2011

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: In this paper we show that certain almost distance-regular graphs, the so-called $h$-punctually walk-regular graphs, can be characterized through the cospectrality of their perturbed graphs. A graph $G$ with diameter $D$ is called $h$-punctually walk-regular, for a given $hleD$, if the number of paths of length $ell$ between a pair of vertices $u,v$ at distance $h$ depends only on $ell$. The graph perturbations considered here are deleting a vertex, adding a loop, adding a pendant edge, adding/removing an edge, amalgamating vertices, and adding a bridging vertex. We show that for walk-regular graphs some of these operations are equivalent, in the sense that one perturbation produces cospectral graphs if and only if the others do. Our study is based on the theory of graph perturbations developed by Cvetkovi'c, Godsil, McKay, Rowlinson, Schwenk, and others. As a consequence, some new characterizations of distance-regular graphs are obtained.

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

Recommendations

• On almost distance-regular graphs
• Dual concepts of almost distance-regularity and the spectral excess theorem
• On \(k\)-walk-regular graphs
• Characterizing \((\ell ,m)\)-walk-regular graphs
• Locally pseudo-distance-regular graphs

zbMATH Keywords

eigenvaluescospectral graphsdistance-regular graphperturbationwalk-regular graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Association schemes, strongly regular graphs (05E30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Developments on spectral characterizations of graphs
• Eigenspaces of graphs
• Problems in algebraic combinatorics
• On almost distance-regular graphs
• The characteristic polynomials of modified graphs
• On Angles and Perturbations of Graphs
• Title not available (Why is that?)
• Characterizing distance-regularity of graphs by the spectrum
• Feasibility conditions for the existence of walk-regular graphs
• Spectral conditions for the reconstructibility of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new family of distance-regular graphs with unbounded diameter
• Algebraic characterizations of distance-regular graphs
• Title not available (Why is that?)
• On pseudo-distance-regularity
• The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs
• Eigenvalues, eigenspaces and distances to subsets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Walk Generating Functions, Christoffel-Darboux Identities and the Adjacency Matrix of a Graph
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• Geometric aspects of 2-walk-regular graphs
• On the spectra and spectral radii of token graphs
• Vertex-removal, vertex-addition and different notions of similarity for vertices of a graph
• On almost distance-regular graphs
• More on Graph Perturbations
• On Angles and Perturbations of Graphs

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

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