5
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ 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 $\endgroup$
    – Gordon Royle
    Commented Mar 26, 2012 at 1:00
  • 3
    $\begingroup$ @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. $\endgroup$
    – Chris Godsil
    Commented Mar 26, 2012 at 3:02
  • $\begingroup$ 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. $\endgroup$
    – Ken W. Smith
    Commented Mar 26, 2012 at 12:38
  • $\begingroup$ 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.... $\endgroup$
    – Ken W. Smith
    Commented Mar 26, 2012 at 14:33

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .