On perturbations of almost distance-regular graphs

Details On perturbations of almost distance-regular graphs On perturbations of almost distance-regular graphs

2012-02-15

arxiv.org/abs/1202.3313v1

Linear Algebra and its Applications 435 (2011), 2626-2638

Mathematics

Combinatorics

Scientific paper

10.1016/j.laa.2011.05.004

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 $h\le D$, 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.

Affiliated with

Also associated with

No associations

Rating

On perturbations of almost distance-regular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On perturbations of almost distance-regular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On perturbations of almost distance-regular graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-557868