Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
5  
Not an answer, but there has been some work done on graphs that are distance-regular from EVERY vertex. Godsil and Shawe-Taylor show that these are either distance-regular (as usual) or distance-biregular (bipartite with each side of the bipartition having its own set of intersection numbers.) See sciencedirect.com/science/article/pii/009589568790027X –  Gordon Royle Mar 26 '12 at 1:00
3  
@Ken: If you have an equitable partition and replace the subgraph induced by one cell with some other regular graph of the same valency, then your partition is still equitable. So the eigenvalues of the quotient are eigenvalues of the modified graph. Your example with the Petersen graph is this operation applied to the distance partition with respect to a vertex. This explains the divisibility by the minimal polynomial in your last paragraph. And the result that Gordon cites is also due (independently) to Delorme. –  Chris Godsil Mar 26 '12 at 3:02
    
Thanks to both of you! "Equitable partition" is the key idea I am after, I think. I'll go ahead and get the JCT(B) article through interlibrary loan. –  Ken W. Smith Mar 26 '12 at 12:38
    
A follow-up -- much of the theory I need seems to be collected in section 9.3 (Equitable Partitions) of Algebraic Graph Theory by 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.... –  Ken W. Smith Mar 26 '12 at 14:33
add comment

1 Answer 1

up vote 0 down vote accepted

The response by Chris Godsil is sufficient as an answer to this question. The general description of these graphs is collected in section 9.3 (Equitable Partitions) of Algebraic Graph Theory by Chris Godsil and Gordon Royle. As a family of graphs, the "equitable partition" requirement is not restrictive enough to get a good handle on what these graphs look like; there are many many more of them than there are distance regular graphs and it is easy to "abuse" a distance regular graph by swapping a few edges and get an equitable partition that is not distance regular.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.