In connection with some work I’m currently doing with Alice Devillers and Simeon Ball, we have come across an interesting subproblem: is there a distance regular graph with intersection array ? It seems that no such graph is known nor proved to not exist. So some background first …
A distance regular graph is a simple connected graph which has a distance distribution diagram. There is a long-winded formal definition of a drg, but we will keep it brief; from every vertex we can say how many are at distance 1, 2, 3 etc and then work out how many common neighbours there are from a vertex at a particular distance, nearer or further than that particular distance. So for an example, take the Heawood graph:
This graph is regular of degree 3, has diameter 3, and there are 6 vertices at distance 2 and 4 vertices at distance 3, from any vertex. What’s more we draw the distance distribution diagram:
In general the parameters of a distance regular graph consist of ‘s and ‘s where for any vertex at distance from , there are exactly neighbours of at distance from , and exactly neightbourse of at distance from .
So we say that the Heawood graph has intersection array , reading left to right. For other reasons that I won’t go into in this post, we were interested in whether a drg on 176 vertices could have parameters . Such a graph would be a particular type of distance regular graph known as a generalised odd graph; a drg with diameter and girth . (These graphs include the odd graphs and the folded cube graphs). So I traced back the problem and found that this question arose in a 1982 paper of Norman Biggs (‘Distance regular graphs with diameter 3’), and was still open in Andries Brouwer’s 1984 follow-up paper (‘Distance regular graphs of diameter 3 and strongly regular graphs’). By merging the distance 1 and 2 relations, we obtain a strongly regular graph and so I guess from Andries’ tables that this problem is still unresolved.
Can anyone out there say whether there is a distance regular graph with parameters ?