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()) 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
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()], 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)
We confirm that $Y$ has girth seven, an increase of one from the girth of $X$. You might verify that $Y$ is distance-transitive.