Self-complementary completions on six vertices

arXiv:2609.20231 · math.CO, cs.AI · Submitted 2026-07-27 · Read on arXiv

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.

Related papers