More about Divisible Design Graphs

D. Crnkovic, W.H. Haemers

Research output: Working paperDiscussion paperOther research output

227 Downloads (Pure)

Abstract

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.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages11
Volume2011-140
Publication statusPublished - 2011

Publication series

NameCentER Discussion Paper
Volume2011-140

    Fingerprint

Keywords

  • divisible design graph
  • divisible design
  • walk-regular graph
  • (v
  • k
  • λ)-graph
  • Hadamard matrix

Cite this

Crnkovic, D., & Haemers, W. H. (2011). More about Divisible Design Graphs. (CentER Discussion Paper; Vol. 2011-140). Operations research.