Exact counting of unlabeled quartic graphs by permutation-cycle aggregation
Abstract
The number of unlabeled regular graphs can be expressed as an average of fixed-point counts over vertex permutations, but evaluating each fixed-point count still requires the degree constraints to be enforced. We give an exact recurrence that processes one complete permutation cycle at a time and records the remaining cycles only by their lengths and residual degrees. The recurrence combines internal edge orbits with orbits joining distinct cycles, while binomial and multinomial coefficients retain the multiplicities of choices that lead to the same remaining state. We prove that this state description is sufficient under complete-cycle elimination and derive bounds on the number of states and transitions. For every fixed degree, the resulting algorithm has an exp(O(√n)) upper bound in the number of vertices, including integer-arithmetic costs. The quartic case requires only four positive residual-degree classes for each cycle length. Small-instance comparisons with a separately implemented, vertex-indexed edge-orbit calculation verify both regular and nonuniform residual-degree inputs. The quartic calculation gives unrestricted and connected counts through order 50, including 22 orders beyond the corresponding reference tables through order 28. Connected counts are recovered by the inverse Euler transform, and all 22 identity-permutation contributions for orders 29--50 agree with the published labeled counts. The nonidentity fixed-point terms at these orders have not been independently recomputed.
Related
- Existence of regular sets in circulant quartic graphs: a complete characterization
- Intersection Orbital Graphs of Permutation Groups and Reconstruction of Simple Groups
- A proof of Lehmer's permutation conjecture for neighbor-swap graphs
- Counting cographs in locally dense graphs
- Counting Minimal Vertex Cutsets and a Gap at 1 for Site Percolation on Vertex-Transitive Graphs
BibTeX
@misc{cheng2026exact,
title = {{Exact counting of unlabeled quartic graphs by permutation-cycle aggregation}},
author = {Yue Cheng and Zhipeng Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.31407},
eprint = {2609.31407},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31407},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact counting of unlabeled quartic graphs by permutation-cycle aggregation
AU - Yue Cheng
AU - Zhipeng Xu
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.31407
UR - https://arxiv.org/abs/2609.31407
AB - The number of unlabeled regular graphs can be expressed as an average of fixed-point counts over vertex permutations, but evaluating each fixed-point count still requires the degree constraints to be enforced. We give an exact recurrence that processes one complete permutation cycle at a time and records the remaining cycles only by their lengths and residual degrees. The recurrence combines internal edge orbits with orbits joining distinct cycles, while binomial and multinomial coefficients retain the multiplicities of choices that lead to the same remaining state. We prove that this state description is sufficient under complete-cycle elimination and derive bounds on the number of states and transitions. For every fixed degree, the resulting algorithm has an exp(O(√n)) upper bound in the number of vertices, including integer-arithmetic costs. The quartic case requires only four positive residual-degree classes for each cycle length. Small-instance comparisons with a separately implemented, vertex-indexed edge-orbit calculation verify both regular and nonuniform residual-degree inputs. The quartic calculation gives unrestricted and connected counts through order 50, including 22 orders beyond the corresponding reference tables through order 28. Connected counts are recovered by the inverse Euler transform, and all 22 identity-permutation contributions for orders 29--50 agree with the published labeled counts. The nonidentity fixed-point terms at these orders have not been independently recomputed.
ER -