On perturbations of almost distance-regular graphs |
| |
Authors: | C Dalfó MA Fiol |
| |
Institution: | a Universitat Politècnica de Catalunya, Dept. de Matemàtica Aplicada IV, Barcelona, Catalonia b Tilburg University, Dept. Econometrics and O.R. Tilburg, The Netherlands |
| |
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 h≤D, if the number of paths of length ? between a pair of vertices u,v at distance h depends only on ?. 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?, Godsil, McKay, Rowlinson, Schwenk, and others. As a consequence, some new characterizations of distance-regular graphs are obtained. |
| |
Keywords: | 05C50 05E30 |
本文献已被 ScienceDirect 等数据库收录! |
|