Central digraphs

  • Leander, Gregor, Technical University of Denmark (Project Participant)
  • Thomassen, Carsten (Project Participant)

    Project Details


    This project is a collaboration between André Kündgen, Associate Professor , California State University
    San Marcos, and Lektor Gregor Leander and Professor Carsten Thomassen, DTU.
    A directed graph is called central if the square of its adjacency matrix has a 1 in each entry.
    Central digraphs are directed analogues of the so-called friendship graphs. Today, central digraphs are of
    interest in cryptography. For example, the bit permutation used in the block cipher PRESENT gives rise to
    a central digraph with 16 vertices.
    It has been conjectured that every central directed graph can be obtained from a standard example by a sequence of simple operations called switchings, and also that it can be obtained from a smaller one by an extension. We disprove these conjectures and present a general extension result which, in particular, shows that each counterexample extends to an infinite family.
    Effective start/end date01/01/201001/01/2011