The Cayley Completion of a Graph
Abstract
A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given G with n vertices and m edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order n on the same vertex set? This defines two invariants, the completion number γ+ (additions only) and the Cayley edit distance γ△ (both), each normalized by m. We show that deciding the edit version is NP-complete already for a fixed cyclic host, by a reduction from Hamiltonian Cycle in which the edit cost of a labeling is n+m−2k when it realizes a longest path with k edges; the optimal cost is m−n+2pp(G), bounded in polynomial time by the matching number. We prove that irregularity alone forces γ+(G)≥ nΔ*/(2m)−1, where Δ* is the least d≥Δ with nd even, computable in linear time from the degree sequence; we characterize equality exactly. It is attained on the star, where γ+(K1,q)=(q−1)/2 and the star maximizes γ+, while γ△ stays bounded by an absolute constant. We determine paths and grids exactly, γ+(Pn)=γ+(Pn □ Pn)=1/(n−1), and show γ△(K1,q)→ 2, not the 3/2 suggested by the additive case. We report an exhaustive certified census of all $995$ connected graphs on at most seven vertices. The degree bound is attained on 89.4% and the two invariants separate strictly on 84.7%, though both rates vary sharply with order: attainment 100%,100%,84.8%,89.7% and separation 0%,61.9%,73.2%,87.7% for n=4,5,6,7, dominated by the $853$ graphs on seven vertices. The star uniquely maximizes both. Edit count and the bi-Lipschitz distortion of the completed host are independent, moving oppositely on stars and paths.Data and certificates at doi:10.5281/zenodo.21852006.
Related
- Cayley graph diameters for fixed cycle types are eventually quasipolynomial
- A non-plain virtually free group with a strictly 2-geodetic Cayley graph
- Cayley-graph density of Thompson's group F: local deletions and finite-window bounds
- Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance
- Minimal Cayley graphs with large chromatic number
BibTeX
@misc{souop2026cayley,
title = {{The Cayley Completion of a Graph}},
author = {Rigobert Fokam Souop and Laurent Bitjoka},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.30894},
eprint = {2608.30894},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30894},
}
RIS
TY - UNPB
TI - The Cayley Completion of a Graph
AU - Rigobert Fokam Souop
AU - Laurent Bitjoka
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.30894
UR - https://arxiv.org/abs/2608.30894
AB - A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given G with n vertices and m edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order n on the same vertex set? This defines two invariants, the completion number γ^+ (additions only) and the Cayley edit distance γ_△ (both), each normalized by m. We show that deciding the edit version is NP-complete already for a fixed cyclic host, by a reduction from Hamiltonian Cycle in which the edit cost of a labeling is n+m−2k when it realizes a longest path with k edges; the optimal cost is m−n+2pp(G), bounded in polynomial time by the matching number. We prove that irregularity alone forces γ^+(G)≥ nΔ^*/(2m)−1, where Δ^* is the least d≥Δ with nd even, computable in linear time from the degree sequence; we characterize equality exactly. It is attained on the star, where γ^+(K_1,q)=(q−1)/2 and the star maximizes γ^+, while γ_△ stays bounded by an absolute constant. We determine paths and grids exactly, γ^+(P_n)=γ^+(P_n □ P_n)=1/(n−1), and show γ_△(K_1,q)→ 2, not the 3/2 suggested by the additive case. We report an exhaustive certified census of all $995$ connected graphs on at most seven vertices. The degree bound is attained on 89.4% and the two invariants separate strictly on 84.7%, though both rates vary sharply with order: attainment 100%,100%,84.8%,89.7% and separation 0%,61.9%,73.2%,87.7% for n=4,5,6,7, dominated by the $853$ graphs on seven vertices. The star uniquely maximizes both. Edit count and the bi-Lipschitz distortion of the completed host are independent, moving oppositely on stars and paths.Data and certificates at doi:10.5281/zenodo.21852006.
ER -