Classification of divisible design graphs with at most 39 vertices

Dmitry Panasenko, Leonid Shalaginov

Published 2021-09-27, updated 2021-11-28Version 3

A $k$-regular graph is called a divisible design graph (DDG for short) if its vertex set can be partitioned into $m$ classes of size $n$, such that two distinct vertices from the same class have exactly $\lambda_1$ common neighbors, and two vertices from different classes have exactly $\lambda_2$ common neighbors. A DDG with $m = 1$, $n = 1$, or $\lambda_1 = \lambda_2$ is called improper, otherwise it is called proper. We present new constructions of DDGs and, using a computer enumeration algorithm, we find all proper connected DDGs with at most 39 vertices, except for three tuples of parameters: $(32,15,6,7,4,8)$, $(32,17,8,9,4,8)$, $(36,24,15,16,4,9)$.