Self-complementary completions on six vertices
math.CO, cs.AI
Submitted: 2026-07-27
Updated: 2026-07-27
License: http://creativecommons.org/licenses/by/4.0/
The gist: Let (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.
Abstract
Let (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 (6)=7. The upper bound is witnessed by (x y 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.