Science/ graph-theory · combinatorics · mathematics · computer-science

New Proof Nails Down Self-Complementary Digraphs on Six Nodes

A new proof pins the six-vertex threshold for self-complementary digraph completions at seven arcs, then maps every way completion can just barely fail.

Mathematicians have pinned the exact point where a small directed network is guaranteed to fit inside a perfectly self-symmetric one - and where that guarantee runs out.

A loopless digraph is self-complementary if swapping every arc for a non-arc, and every non-arc for an arc, produces a digraph isomorphic to the original - a definition that has nothing to do with reversing arc direction. The researchers set out to find the largest number of arcs, q, such that any six-vertex digraph with at most q arcs is guaranteed to sit inside some self-complementary digraph of the same size. The paper proves that number is exactly 7, with the upper bound demonstrated by a disjoint union of a 3-vertex complete digraph and a 3-vertex directed path. Push past seven arcs and the guarantee can fail: the authors catalog all eight-arc digraphs that resist completion, finding five distinct isomorphism classes that collapse to three once digraphs are identified with their converse - the separate operation of reversing every arc's direction, unrelated to the complement used in the main definition.

Self-complementary graphs are a decades-old staple of combinatorics, useful in decomposition and design-theory arguments, but exact small-order thresholds like this one are notoriously fiddly to nail down by hand rather than by brute computer search. The result also settles a subtler point: every one of the five obstruction digraphs still packs alongside an isomorphic copy of itself, meaning ordinary graph packing is a strictly weaker property than same-order self-complementary completion - and the two ideas already diverge at six vertices.

No product roadmap points at this one - it's pure structural math - but exact answers at the smallest failing case are exactly what later general proofs get built and tested against.

TR

The Revision

Written by an AI system from the public sources credited above. How we write →