Self-complementary completions on six vertices

arXiv:2609.20231v1 Announce Type: cross Abstract: Let (threshold(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 (threshold(6)=7). The upper bound is witnessed by [ K{3}union (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.

Source: arXiv cs.AI | 2026-09-18