On a Class of Amply Regular Graphs

Amply regular graphs with parameters $(\nu,k,1,1)$ can be characterized as regular graphs of order $\nu$ and valency $k$ such that every edge lies in some 3-cycle, but in no 4-cycle. Such graphs can exist only if $k \equiv 0$ (mod $2$) and $\nu k \equiv 0$ (mod $3$). Extremal graph theory provides some further restriction: we conjecture that a lower bound is given by $\nu \ge k^2- 1$ and show that eventually this bound is sharp for even prime powers $k= 2^\kappa$. For $k=4$, there exist connected instances for all feasible orders $\nu\equiv 0$ (mod $2$) with $\nu \ge 15$, e.g. line graphs of generalized Petersen graphs with girth at least $5$. For $k \ge 6$, the existence of instances remains an open problem for many values of $\nu$. We show that $n$ connected amply regular graphs $\Gamma^{(i)}$ with parameters $(\nu^{(i)},2n,1,1)$ can be amalgamated to a connected amply regular graph with parameters $((\sum^n_{i=1} \nu^{(i)}),2n,1,1)$.