We are interested in distance-regular antipodal covers of $K_n$. First we explain `cover'. We construct a cover of index $r$ of a graph $X$ (or an $r$-fold cover) as follows. Choose a function $f$ from the arcs (ordered pairs of adjacent vertices of $X$) to the symmetric group $\sym r$, such that \[ F((v,u)) =f((u,v))^{-1} \] The vertex set of the cover $X^f$ is \[ V(X)\times \{1,\ldots,r\} \] and $(u,i)\sim (v,j)$ if $j = i^{f(u,v)}$. Less formally, we replace each vertex of $V(X)$ by a coclique of size $r$, and cocliques corresponding to adjacent vertices are joined by a matching of size $r$. The $r$-cocliques are called the fibers of the cover.

A cover $X^f$ is antipodal if its diameter is $d$ and two vertices are in the same fiber if and only they are at distance $d$. The 3-cube is an antipodal cover of $K_4$ with index two and diameter three. The line graph of the Petersen graph is an antipodal cover of $K_5$ with index and diameter three.

Here we are concerned with distance-regular antipodal covers of complete graphs $K_n$. Such covers must have diameter three. There are four obvious parameters $(n,r,a_1,c_2)$, although these are not independent, in fact counting edges joining neighbors of $u$ to vertices at distance two from $u$, we get \[ n(n-2-a_2) = n(r-1)c_2 \] whence \begin{equation} \label{eq:n1rc2} n-1-rc_2 = a_1-c_2. \end{equation} The difference $a_1-c_2$ occurs frequently, and we denote it by $\de$. It is not too hard to show that an antipodal cover of $K_n$ is distance regular if its diameter is three and any two distinct non-adjacent vertices have $c_2$ common neighbors.

Our basic problem is to determine the parameter triples $(n,r,c_2)$ for which a cover exists. This is an impossible problem, so we settle for generating parameter sets for which there is a good chance that a cover exists. Here our first design question surfaces: do we want to order our parameters by $n$ and then $r$ (lexicographically), or by $nr$ then $r$ (for example). We arbitrarily select the first approach.

As a first step we aim to generate a list of quadruples $(n,r,a_1,c_2)$. Now we know that \begin{equation} \label{eq:rbnd} 2\le r\le n-1. \end{equation} What about $c_2$. The neighborhood of a vertex induces a regular graph on $n-1$ vertices with valency $a_1$, whence $na_1$ must be even. From (\ref{eq:n1rc2}) we have \[ n-1-a_1 = (r-1)c_2, \] from which we infer that if $n$ is odd and $r$ is even, then $c_2$ must be even. We also have \begin{equation} \label{c2bnd} 1\le c_2 \le \left\lfloor\frac{n-1}{r-1}\right\rfloor \end{equation}

    def nrc( n):
        lim = (n-1)/(r-1)
        return [(n,r,c) for r in [2..n-1]\ 
         for c in [1..lim] and n*(r-1)*c % 2 == 0]
    def get_a( n, r, c):
        return n, r, n-1-(r-1)*c, c

So we will generate a sequence of 4-tuples, and filter out the ones that obviously do not work. The most useful condition rests on the formulas for the multiplicities of the eigenvalues. As a distance-regular graph with diameter three, a drackn has exactly four distinct eigenvalues \[ n > \th > -1 > \tau \] where $n$ is simple, $-1$ has multiplicity $n-1$ and $-\th\tau=n-1$. The eigenvalues $\th$ and $\tau$ are the zeros of \[ t^2 -\de t - (n-1). \] It is their multiplicities that interest us. With an obvious notation we have \begin{align*} rn &= 1 + (n-1) +m_\th+m_\tau\\ 0 &= (n-1) +(n-1)(-1) +m_\th\th+m_\tau\tau \end{align*} and therefore \begin{equation} \label{eq:mult} m_\th = \frac{(r-1)n(-\tau)}{\th -\tau}. \end{equation}

Two cases arise. First, if $\th$ and $\tau$ are not integers, then \[ \th=\sqrt{n-1},\quad \tau=-\sqrt{n-1} \] and their multiplicities are equal to $n(r-1)/2$. Otherwise they are integers and consequently the discriminant \begin{equation} \label{eq:discr} (\th-\tau)^2 = \de^2+4(n-1) = (a_1-c_2)^2+4(n-1) \end{equation} must be a perfect square. (Note that $\de=n-1-rc_2$.) If this is a perfect square we can determine $\th$ and $\tau$, and then check that our formula for $m_th$ is an integer.

def mult_chk( n, r, a, c):
    disc = (a-c)^2+4*(n-1)
    if is_square(disc):
        sqroot = sqrt( disc)
        theta = (a-c+sqroot)/2
        tau = (a-c-sqroot)/2
        mth = n*(r-1)*theta/sqroot
        mtau = n*(r-1)-mth
        return (theta, tau, mth, mtau)
    else:
        return False

How do we generate 4-tuples? The simplest approach is to use CartesianProduct, but a more efficient strategy is to use generators.

Now we can generate a selected family of 4-tuples. There are other conditions that must hold, we write a predicate for each of these and then write a function that takes a 4-tuple and applies each term in a list of predicates. Note that, when a parameter set is eliminated we need to know at least one of the predicates that it fails.

There is a very strong case to be made that a better parameterization is available. The idea is to search on triples \[ (-\tau,\theta, r) \] Our approach above throws out most triples because $(a_1-c_2)^2+4(n-1)$ is not a perfect square. Our alternative approach only produces triples where this condition is satisfied. We need to treat separately the case where $m_\th=m_\tau$, (equivalently $\de=0$) but this makes sense combinatorially. If we want the parameters for covers of $K_n$ with index $r$, then we filter through the pairs $(-\tau, \theta)$ where $\theta$ runs over the elements of divisors(n-1) such that the Krein bound holds.