Self-complementary completions on six vertices

Abstract: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 \[ \bK{3}\dunion (x\longrightarrow y\longrightarrow 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.

Combinatorics (math.CO); Artificial Intelligence (cs.AI)

arXiv:2609.20231 [math.CO]

(or arXiv:2609.20231v1 [math.CO] for this version)

https://doi.org/10.48550/arXiv.2609.20231 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

generate_certificates.py

minimality_certificates.txt

verification_output_cpp.txt

verification_output_python.txt

verify_digraph.cpp

verify_independent.py

(2 additional files not shown) You must enabled JavaScript to view entire file list.

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.