Walk regular divisible design graphs

Dean Crnkovic, W. H. Haemers

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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,\lambda )-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
Original languageEnglish
Pages (from-to)165-175
JournalDesigns, Codes and Cryptography
Volume72
Issue number1
DOIs
Publication statusPublished - Jul 2014

    Fingerprint

Keywords

  • divisible design graph
  • divisible design
  • walk-regular graph
  • Hadamard matrix

Cite this