1 Discrete mathematics, Department of Mathematics, Technical University of Denmark2 Department of Mathematics, Technical University of Denmark3 unknown4 Department of Applied Mathematics and Computer Science, Technical University of Denmark
A directed graph is called central if its adjacency matrix A satisfies the equation A2=J, where J is the matrix with a 1 in each entry. 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.
Journal of Combinatorial Theory, Series a, 2011, Vol 118, Issue 7, p. 2025-2034
Unique path property; Central directed graph; Central groupoid