More about Divisible Design Graphs

Abstract: Divisible design graphs (DDG for short) have been recently defined by Kharaghani, Meulenberg and the second author as a generalization of (v, k, λ)-graphs. In this paper we give some new constructions of DDGs, most of them using Hadamard matrices and (v, k, λ)-graphs. For three parameter sets we give a nonexistence proof. Furthermore, we find conditions for a DDG to be walk-regular. It follows that most of the known examples are walk-regular, but some are not. In case walk-regularity of a DDG is forced by the parameters, necessary conditions for walk-regularity lead to new nonexistence results for DDGs. We examine all feasible parameter sets for DDGs on at most 27 vertices, establish existence in all but one cases, and decide on existence of a walk-regular DDG in all cases.