Skip to content

A mysterious generalised odd graph

October 30, 2011

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\}?

2 Comments leave one →
  1. November 12, 2011 7:40 am

    Thank to Tim Penttila for pointing out some typos in this post!


  1. Weekly Picks « — the Blog

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: