# 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 |