Regular Graphs with Pairwise Distinct K_t-Degrees
For a fixed integer \(t \ge 3\), let \(\kappa_t(v)\) denote the number of copies of \(K_t\) containing a vertex \(v\). We prove that for every \(t \ge 6\) and every sufficiently large even integer \(r\), there exists an explicit connected \(r\)-regular graph on \(2r+2\) vertices whose vertex \(K_t\)-degrees are pairwise distinct. The construction is uniform in \(t\) and \(r\) and has order linear in the regularity. Its analysis uses exact binomial clique-count formulas, a reflection order that localises possible collisions, polynomial noncancellation, and a uniform root bound. For \(6 \le t \le 15\), exact integer certification of the same construction improves the sufficient condition to every even \(r \ge 12(t-2)\). This record contains the manuscript together with the mathematical supplementary material and the exact-arithmetic verification archive supporting the fixed-order result. The verification archive includes certificate streams, reconstruction code, integrity metadata, and exact finite checks.
Authors
- Zhanhe Zhang (ORCID: https://orcid.org/0009-0007-2883-9640)
- Hao Ying
Institutions
- Central University of Finance and Economics (CN)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-04
- DOI
- https://doi.org/10.5281/zenodo.23133287
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint