Chapter 4. Distance-Regular Graphs

Table of Contents

Distance Regularity
Generalized Quadrangles
The McLaughlin Graph
Drackns: Generating Parameter Sets

Distance Regularity

First some code to allow us to test if a graph is distance regular. The main use of this is to provide a test that some graph we have constructed is distance regular.

def distance_partition( X, vxi):
    xvs = X.vertices()
    E = dict()
    for vxj in xvs:
        dj = X.distance(vxi, vxj)
    return E.values()    

If $X$ is distance-regular, then the distance partition is equitable and the quotient matrix with respect to this partition is the same for all vertices.

We use the Kneser graphs as a test case, though we must relabel the vertices to convert them from sets to integers.

X = graphs.KneserGraph(7, 3)
dp = distance_partition( X, X.vertices()[0])
X.is_equitable( dp, quotient_matrix=True) 
[0 4 0 0]                               
[1 0 3 0]                               
[0 1 0 3]                               
[0 0 2 2]

If the partition is not equitable, the response would be a simple False.

Many distance-regular graphs are distance-transitive. We can test for this by verifying that our graph is vertex transitive and the number of orbits of the stabilizer of a vertex is the diameter plus one.

orbs = X.automorphism_group( return_group=0, orbits=1)
len(orbs) == 1 
pn = [ [X.vertices()[0]], X.vertices()[1:]]
grp = X.automorphism_group( partition=pn)
len( grp.orbits()) == X.diameter() + 1

The Kneser graph has a perfect 1-code---a set of seven vertices pairwise at distance three. If we delete the vertices in a perfect 1-code, the resulting graph is the Coxeter graph which is a distance-regular cubic graph. It is not too hard to see that a perfect 1-code will be a coclique of size seven that is maximal under inclusion. So we can find one and construct the Coxeter graph as follows.

colqs = X.complement().cliques_maximal()
colqs7 = filter( lambda it: len(it)==7, colqs)
Y = X.copy()
Y.delete_vertices( colqs7[0])

We confirm that $Y$ has girth seven, an increase of one from the girth of $X$. You might verify that $Y$ is distance-transitive.

X.girth(), Y.girth()
(6, 7)