Metraipolis › archive › dc_d4734ab2ac2a
The Cayley Completion of a Graph — arXiv:2608.30894
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.30894
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T09:31:22.661Z
- SHA-256 of the archived text
8ad19029669dc82f5025563b02e1ad0612193f77d39d219bd050d98a7858763d- Stable URL of this page
https://metraipolis.com/documento/dc_d4734ab2ac2a
How to cite
The Cayley Completion of a Graph — arXiv:2608.30894 — arXiv (en), https://arxiv.org/abs/2608.30894 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d4734ab2ac2a (Metraipolis archive dc_d4734ab2ac2a, sha256 8ad19029669dc82f5025563b02e1ad0612193f77d39d219bd050d98a7858763d)
BibTeX
@misc{dcd4734ab2ac2a,
title = {The Cayley Completion of a Graph — arXiv:2608.30894},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.30894},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d4734ab2ac2a; sha256 8ad19029669dc82f5025563b02e1ad0612193f77d39d219bd050d98a7858763d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.30894. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\gamma^{+}$ (additions only) and the Cayley edit distance $\gamma_{\triangle}$ (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 $\gamma^{+}(G)\ge n\Delta^{*}/(2m)-1$, where $\Delta^{*}$ is the least $d\ge\Delta$ with $nd$ even, computable in linear time from the degree sequence; we characterize equality exactly. It is attained on the star, where $\gamma^{+}(K_{1,q})=(q-1)/2$ and the star maximizes $\gamma^{+}$, while $\gamma_{\triangle}$ stays bounded by an absolute constant. We determine paths and grids exactly, $\gamma^{+}(P_n)=\gamma^{+}(P_n\,\square\,P_n)=1/(n-1)$, and show $\gamma_{\triangle}(K_{1,q})\to 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 this http URL and certificates at doi: https://doi.org/10.5281/zenodo.21852006 .
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-01 in math.CO).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.30894 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T09:02:28.887Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).