Project Details
Description
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.
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.
| Status | Finished |
|---|---|
| Effective start/end date | 01/01/2010 → 01/01/2011 |
Collaborative partners
- Technical University of Denmark (lead)
- Technical University of Denmark (Project partner)
- California State University (Project partner)