Conditions for the Parameters of the Block Graph of Quasi-Symmetric Designs

  • Rajendra M. Pawale
  • Mohan S. Shrikhande
  • Shubhada M. Nyayate
Keywords: Quasi-symmetric design, Strongly regular graph, Block Graph


A quasi-symmetric design (QSD) is a 2-$(v,k,\lambda)$ design with intersection numbers $x$ and $y$ with $x< y$. The block graph of such a design is formed on its blocks with two distinct blocks being adjacent if they intersect in $y$ points. It is well known that the block graph of a QSD is a strongly regular graph (SRG) with parameters $(b,a,c,d)$ with smallest eigenvalue $ -m =-\frac{k-x}{y-x}$.

The classification result of SRGs with smallest eigenvalue $-m$, is used to prove that for a fixed pair $(\lambda\ge 2,m\ge 2)$, there are only finitely many QSDs. This gives partial support towards Marshall Hall Jr.'s conjecture, that for a fixed $\lambda\ge 2$, there exist finitely many symmetric $(v, k, \lambda)$-designs.

We classify QSDs with $m=2$ and characterize QSDs whose block graph is the complete multipartite graph with $s$ classes of size $3$. We rule out the possibility of a QSD whose block graph is the Latin square graph $LS_m (n)$ or complement of $LS_m (n)$, for $m=3,4$.

SRGs with no triangles have long been studied and are of current research interest. The characterization of QSDs with triangle-free block graph for $x=1$ and $y=x+1$ is obtained and the non-existence of such designs with $x=0$ or $\lambda > 2(x+2)$ or if it is a $3$-design is proven. The computer algebra system Mathematica is used to find parameters of QSDs with triangle-free block graph for $2\le m \le 100$. We also give the parameters of QSDs whose block graph parameters are $(b,a,c,d)$ listed in Brouwer's table of SRGs.

Article Number