Self-complementary completions on six vertices
Not on the map. Why?
Abstract (arXiv)
Let (cthreshold(n)) be the largest integer (q) such that every loopless digraph on (n) vertices with at most (q) arcs is isomorphic to a spanning subdigraph of a self-complementary digraph of order (n). We prove that (cthreshold(6)=7). The upper bound is witnessed by [ bK3dunion (xlongrightarrow ylongrightarrow z), ] and follows from a direct argument with a self-complementing permutation. We also determine the complete eight-arc obstruction layer: it consists of five isomorphism classes, or three after converse digraphs are identified. All five are arc-minimal. Each nevertheless packs with an isomorphic copy of itself, so ordinary packing is strictly weaker than same-order self-complementary completion already at this first failure layer.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 0 of its 4 references that are in the map. First posted on arXiv 27 Jul 2026.
Builds on
0 of 4 references.
No references here yet.
Built on by
Not cited yet.