{
  "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 $γ_{\\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 $γ^{+}(G)\\ge nΔ^{*}/(2m)-1$, where $Δ^{*}$ is the least $d\\geΔ$ 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 $γ_{\\triangle}$ stays bounded by an absolute constant. We determine paths and grids exactly, $γ^{+}(P_n)=γ^{+}(P_n\\,\\square\\,P_n)=1/(n-1)$, and show $γ_{\\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 paths.Data and certificates at doi:10.5281/zenodo.21852006.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2608.30894",
  "author_total": 2,
  "authors": [
    {
      "name": "Rigobert Fokam Souop"
    },
    {
      "name": "Laurent Bitjoka"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/a34v8d8sfntsd.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2608.30894",
  "fulltext_url": null,
  "id": "a34v8d8sfntsd",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2608.30894",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DM"
    ],
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "2607|Finite Group Theory Research"
    ]
  ],
  "openalex": "W7204873842",
  "pdf_url": "https://arxiv.org/pdf/2608.30894",
  "pmcid": null,
  "pmid": null,
  "published": "2026-08-31",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/a34v8d8sfntsd.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:17:48Z",
      "native_id": "2608.30894",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2608.30894"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "The Cayley Completion of a Graph",
  "title_text": "The Cayley Completion of a Graph",
  "type": "preprint",
  "updated_at": "2026-10-30T12:17:48Z",
  "url": "https://research.draconitic.com/paper/a34v8d8sfntsd",
  "venue": "arXiv",
  "versions": []
}