Switchings, extensions, and reductions in central digraphs

André Kündgen, Gregor Leander, Carsten Thomassen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    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.
    Original languageEnglish
    JournalJournal of Combinatorial Theory, Series A
    Volume118
    Issue number7
    Pages (from-to)2025-2034
    ISSN0097-3165
    DOIs
    Publication statusPublished - 2011

    Keywords

    • Unique path property
    • Central directed graph
    • Central groupoid

    Fingerprint

    Dive into the research topics of 'Switchings, extensions, and reductions in central digraphs'. Together they form a unique fingerprint.

    Cite this