标题： 关于几乎距离正则图的扰动 显示英文标题

标题： On perturbations of almost distance-regular graphs

摘要： 在本文中，我们证明了某些几乎距离正则图，即所谓的$h$-点步行正则图，可以通过其扰动图的共谱性来表征。 一个直径为$D$的图$G$被称为$h$-punctually walk-regular，对于给定的$h\le D$，如果一对顶点$u,v$在距离$h$处的长度为$\ell$的路径数量仅取决于$\ell$。 这里的图扰动包括删除一个顶点、添加一个环、添加一个悬挂边、添加/移除一条边、合并顶点以及添加一个桥接顶点。 我们证明了对于行走正则图，这些操作中的一些在某种意义上是等价的，即一种扰动产生共谱图当且仅当其他扰动也如此。 我们的研究基于Cvetković、Godsil、McKay、Rowlinson、Schwenk等人发展起来的图扰动理论。 作为结果，得到了一些距离正则图的新特征。 显示英文摘要

摘要： 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.