engleski

Walk-regular divisible design graphs

A divisible design graph (DDG for short) is a graph whose adjacency matrix is the incidence matrix of a divisible design. DDGs were introduced by Kharaghani, Meulenberg and the second author as a generalization of (v, k, λ)-graphs. It turns out that most (but not all) of the known examples of DDGs are walk-regular. In this paper we present an easy criterion for this to happen. In several cases walk-regularity is forced by the parameters of the DDG ; then known conditions for walk-regularity lead to nonexistence results for DDGs. In addition, we construct some new DDGs, and check old and new constructions for walk-regularity. In doing so, we present and use special properties in case the classes have size two. All feasible parameter sets for DDGs on at most 27 vertices are examined. Existence is established in all but one case, and existence of a walk-regular DDG in all cases.

Divisible design graph ; Divisible design ; Walk-regular graph ; (v, k, λ)-graph ; Hadamard matrix

nije evidentirano