PreprintCC BY 4.0arXiv
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 bK3dunion (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
- A parity constraint on the topological numbers of self-complementary triply-periodic surfaces
- Krasner Completions of Filtered Bands
- Lp Convergence of AMV Laplacians on completions of Riemannian manifolds
- Tropicalization and Polyhedral Completions of Weyl Algebras
- p-adic Hodge theory of unipotent completions revisited
BibTeX
@misc{dai2026selfcomplementary,
title = {{Self-complementary completions on six vertices}},
author = {Xinan Dai and Wenhao Deng and Yingdong Shi and Tailin Wu and Yuchen Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20231},
eprint = {2609.20231},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20231},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Self-complementary completions on six vertices
AU - Xinan Dai
AU - Wenhao Deng
AU - Yingdong Shi
AU - Tailin Wu
AU - Yuchen Yang
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.20231
UR - https://arxiv.org/abs/2609.20231
AB - 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 (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.
ER -