## 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)
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)