**Table of Contents**

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) E.setdefault(dj,[]).append(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) X.relabel() 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

True

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

True

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)