{"id":"arxiv/2608.30894","url":"https://arxiv.org/abs/2608.30894","tags":["cs.DM","cs.DS","math.CO"],"score":0,"title":"The Cayley Completion of a Graph","domain":"cs.DM","source":"arxiv","authors":["Rigobert Fokam Souop","Laurent Bitjoka"],"reviews":0,"subject":"cs.DM","summary":"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 $γ_{\\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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-31","reactions":{}}