Graph Saturation Numbers for Small Subgraphs: Exact Computations via SAT

Read full text Summarise with VIRAT
Authors: Alexander Richard Towell
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Exact small-order C6 saturation values and complete minimum-graph classifications, by Alexander Richard Towell. The exact values at orders 11, 12, 13, 14, and 15 are respectively 14, 16, 17, 19, and 20. Complete minimum families at orders 11–14 contain 1, 35, 4, and 205 isomorphism classes. Order 15 is not classified. New in v5: the complete 205-class order-14 minimum family, obtained by checking all 342,260,293 unlabeled 19-edge graphs with two separate property implementations and independently checking every accepted witness; and sat(15,C6)=20, proved by rejecting all 784,526,109 unlabeled graphs through 19 edges with both implementations and verifying a 20-edge witness. Correction and attribution: Remark 1, page 1089, of Zhang, Luo, and Shigeno (2015), doi:10.1007/s00373-014-1422-4, reports 15 at order 11. Our explicitly certified 14-edge saturated graph contradicts that small-order computational claim; the general upper-bound theorem is unaffected. The final paper already records sat(12,C6)=16, so the addition there is the complete 35-class classification. The order-9 and order-10 values and families are also prior work; earlier novelty claims for those results are withdrawn. Lan et al. (2025), doi:10.1016/j.disc.2025.114504, already supply matching upper bounds at orders 12–15. The new order-15 contribution is its exhaustive lower bound and exactness, not the upper-bound construction. No general or asymptotic improvement is claimed. The supporting archive retains byte-exact graph6 families, a hand-checkable order-11 certificate, code, tests, coverage reports, full enumeration logs, and source/input hashes. Per-edge counts match a separate exact-integer Polya–Burnside calculation. Both compiled property implementations share the nauty generator; this is independent checking, not independent generation. Count agreement alone does not prove completeness. The evidence is reproducible computational proof, not formal proof-assistant or SAT proof-trace certification. Earlier SAT examples are retained as validation material.

Fields of Study & Subjects

Limits and Structures in Graph Theory Advanced Graph Theory Research Advanced Combinatorial Mathematics

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
25 March 2026
Language
EN
Document type
Preprint