A distance-regular graph (DRG) is, in essence, a graph $\Gamma$ of diameter $d$ for which there are integers $c_i, a_i, b_i, (0 \le i \le d)$ such that for *all* vertices $x$ of $\Gamma$ and for all vertices $y$ of distance $i$ from $x$, the number of vertices $z$ adjacent to $y$ and distance $i-1$ from $x$ is $c_i$; the number of vertices $z$ adjacent to $y$ for distance $i$ from $x$ is $a_i$ and the number of $z$ adjacent to $y$ of distance $i+1$ from $x$ is $b_i.$
(See the paragraph on intersection numbers in this Wikipedia article on DRGs.)

For example, the Petersen graph is distance-regular of diameter 2. For the Petersen graph the intersection numbers are $b_0=3, b_1=2; a_1=0, a_2=2; c_1=1, c_2=1.$

Two recent research projects (one with undergraduates) have led me to some graphs that satisfy a weaker condition -- they satisfy the conditions above for *some*, but not all vertices $x$. These graphs are not distance regular but *look* distance regular with respect to a particular vertex, that is, the intersection numbers $c_i, a_i, b_i$ are well-defined for the distributions of vertices of distance $i$ from the special vertex $x.$

For example, fix a particular vertex $x_0$ in the Petersen graph and consider the six vertices not adjacent to $x_0$. These vertices lie on a hexagon, a cycle of length six. Replace that hexagon by two triangles. This new graph is no longer distance regular, but the integers $b_0, ..., c_2$ still count distributions of vertices with respect to that special vertex $x_0.$

**Question.** Is there a theory of these "local" distance-regular graphs? Do they have a name? (I think "locally distance-regular" is taken? There are a variety of generalizations of distance-regular graphs; a google search reveals "almost-" and "pseudo-" but none of those generalizations seem to quite describe my need for a graph which has at least one vertex $x$ with intersection numbers.)

These "local" distance-regular graphs are fairly common in the sense that one can deform almost any distance regular graph into one of these "local" distance-regular graphs in a manner similar to the way the Petersen graph was deformed, above.

I can show that some of the properties of DRGs persist in these generalizations, for example, the minimal polynomial of the DRG divides the minimal polynomial of the ``deformed" not-quite-distance-regular graph and so the eigenvalues of the DRG are a subset of the eigenvalues of the not-quite DRG. In many cases these "not-quite" DRGs have few eigenvalues.

Algebraic Graph Theoryby Chris Godsil and Gordon Royle (of course!) -- which I own and is sitting on my desk! I thank you both and I apologize for not putting these ideas together.... $\endgroup$ – Ken W. Smith Mar 26 '12 at 14:33