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 $\{7, 6, 6;1, 1, 2\}$? 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 $b_i$‘s and $c_i$‘s where for any vertex $w$ at distance $i$ from $v$, there are exactly $c_i$ neighbours of $w$ at distance $i-1$ from $v$, and exactly $b_i$ neightbourse of $w$ at distance $i+1$ from $v$.

So we say that the Heawood graph has intersection array $\{3, 2, 2; 1, 1, 3\}$, 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 $\{7,6,6;1,1,2\}$. Such a graph would be a particular type of distance regular graph known as a generalised odd graph; a drg with diameter $d$ and girth $2d+1$. (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 $\{7,6,6;1,1,2\}$?