On perturbations of almost distance-regular graphs

DOI10.1016/J.LAA.2011.05.004MaRDI QIDQ550646zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

cospectral graphsdistance-regular grapheigenvaluesperturbationwalk-regular graph

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cites work

• A new family of distance-regular graphs with unbounded diameter
• Algebraic characterizations of distance-regular graphs
• Characterizing distance-regularity of graphs by the spectrum
• Developments on spectral characterizations of graphs
• Eigenspaces of graphs
• Eigenvalues, eigenspaces and distances to subsets
• Feasibility conditions for the existence of walk-regular graphs
• scientific article; zbMATH DE number 4135984 (Why is no real title available?)
• scientific article; zbMATH DE number 3968632 (Why is no real title available?)
• scientific article; zbMATH DE number 3655975 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 17788 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 3556146 (Why is no real title available?)
• scientific article; zbMATH DE number 3585485 (Why is no real title available?)
• scientific article; zbMATH DE number 1028230 (Why is no real title available?)
• scientific article; zbMATH DE number 863484 (Why is no real title available?)
• On almost distance-regular graphs
• On Angles and Perturbations of Graphs
• On pseudo-distance-regularity
• Problems in algebraic combinatorics
• Spectral conditions for the reconstructibility of a graph
• The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs
• The characteristic polynomials of modified graphs
• Walk Generating Functions, Christoffel-Darboux Identities and the Adjacency Matrix of a Graph

Cited in

(7)

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

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)