Source-linked AI summary
The Cayley Completion of a Graph
Rigobert Fokam Souop, Laurent Bitjoka
TL;DR
The paper asks how few edge additions or edits are needed to turn a graph into an abelian Cayley graph on the same vertex set. It studies these invariants through hardness reductions, structural bounds, exact evaluations, and a certified census, showing that fixed-host editing is NP-complete while degree-based completion bounds and extremal examples clarify the landscape.
Problem
The paper measures how far finite connected graphs are from abelian Cayley graphs on the same vertex set using additions-only and addition-and-deletion invariants.
Method
The paper combines a Hamiltonian Cycle reduction, generator-class structure, degree-sequence bounds, exact graph analyses, and exhaustive certified enumeration.
Results
Fixed cyclic-host editing is NP-complete, the degree bound is attained on 89.4% of the census, and the star uniquely maximizes both invariants among connected graphs on at most seven vertices.
Takeaways & Limitations
The degree bound is a useful triage filter for additions-only completion but does not capture the difficulty of edit completion, while the star and other exact families delimit the invariants.
Takeaways & Limitations
Fixed-parameter tractability remains open because even the zero-edit case requires recognizing abelian Cayley graphs, for which no general polynomial algorithm is known.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper measures how many edge additions or edits are needed to turn a connected graph into an abelian Cayley graph on the same vertex set. It proves hardness, derives a degree-based obstruction, determines key families, and validates the invariants through a certified graph census.
- Motivation: The completion number γ+ permits additions only, while the Cayley edit distance γ△ permits additions and deletions, both normalized by the original edge count.The approach keeps the vertex set fixed rather than enlarging the host.
- Hardness: The fixed-cyclic-host edit problem is NP-complete, with labeling cost n + m − 2k when k edges map to consecutive pairs.The reduction is from Hamiltonian Cycle, so the computational difficulty lies in finding the labeling.
- Degree obstruction: The degree lower bound is attained on 89.4% of the census, but it does not capture generator-class feasibility, the source of the harder labeling problem.The star attains equality and has γ+(K1,q) = (q − 1)/2.
- Exact families and census: The paper exactly determines stars, paths, grids, and cyclic edits, including γ△(K1,q) = (2q − 3)/q and γ+(Pn) = γ+(Pn□Pn) = 1/(n − 1).The certified census covers all 995 connected graphs on at most seven vertices, while the related-work discussion contrasts fixed-vertex distance with enlarged-host embeddings and zero-set classification.
- Census: The census enumerates connected graphs through seven vertices using the Atlas of Graphs ordering.The paper also reports that the two invariants separate strictly on 84.7% of the census.
3 Definitions
The invariants minimize normalized edge changes over abelian groups, vertex labelings, and symmetric generating sets, with additions-only completions required to contain the original graph. Translation invariance and inverse-pair classes reduce the search structure.
- Definitions: For an order-n abelian group Γ, a bijection labels G's vertices, and a symmetric generating set S defines the Cayley host Cay(Γ,S).The host uses edges joining x to x + s for s in S.
- Definitions: The additions-only invariant requires Eπ(G) ⊆ E(Cay(Γ,S)), while the edit invariant allows both host-edge additions and graph-edge deletions.The completed graph must itself be the Cayley host, so it is regular.
- Definitions: Both invariants are normalized by m, vanish exactly for abelian Cayley graphs, and satisfy γ△ ≤ γ+.The inequality is strict for a large majority of the census graphs.
- Search reduction: Translation invariance permits one vertex label to be fixed at zero, reducing the labeling search from n! to (n − 1)! possibilities.This normalization supports exhaustive rather than heuristic census computation.
- Class decomposition: Each inverse-pair generator class contributes either a perfect matching or equal-length cycles, so host structure is organized by class contributions.For a fixed labeling, the cost depends on the class-count vector and admissible generator-class subset.
5 The degree lower bound
Irregularity forces a computable lower bound on additions because every abelian Cayley completion is regular. Equality has an exact structural characterization: the graph must span a minimum-degree regular abelian Cayley host.
- Lower bound: The degree bound is γ+(G) ≥ nΔ*/(2m) − 1, where Δ* is the least d ≥ Δ such that nd is even.The bound follows because an additions-only completion cannot lower degrees and a d-regular n-vertex graph has nd/2 edges.
- Computability and census: The bound is computable in linear time from the degree sequence and is attained on 89.4% of the 995-graph census, with correlation r = 0.851 to γ+.It can triage graphs without running a labeling search.
- Scope: The bound captures only the obstruction imposed by irregularity, not whether added edges form legitimate generator classes.That missing feasibility condition is tied to the hardness of the completion problem.
- Equality characterization: Equality holds exactly when G is a spanning subgraph of a Δ*-regular abelian Cayley graph on the same vertex set.The converse constructs a valid completion by adding the host edges absent from G.
- Parity correction: The parity correction is decisive: the sharpened bound is attained on 890 of 995 graphs, compared with 476 under the plain form.At n = 5 attainment rises to 100%, and at n = 7 to 89.7%; even orders remain unchanged.
6 Exactly determined families
Several graph families admit exact completion values. Stars separate the two invariants most sharply, while paths and grids share the same normalized additive completion value.
- Stars: γ+(K1,q) = (q − 1)/2, achieved by completing the star to Kq+1; thus additive completion grows without bound with q.The complete graph is an optimal additive host because it meets the degree lower bound.
- Stars: γ△(K1,q) = (2q − 3)/q for q ≥ 2, attained by a cycle host, and therefore γ△(K1,q) → 2 rather than 3/2.The construction preserves two pendant edges, deletes the other star edges, and adds the remaining cycle edges.
- Stars: Allowing deletions changes the star behavior from unbounded γ+ to bounded γ△, with the star uniquely maximizing γ△ in the census.Optimal hosts found computationally are cycles for every 3 ≤ q ≤ 8.
- Paths and grids: γ+(Pn) = 1/(n − 1), because one endpoint edge completes the path to Cn.The path is nonregular, so zero additions cannot suffice.
- Paths and grids: γ+(Pn□Pn) = 1/(n − 1), because 2n wrap-around edges produce the torus Cn□Cn.The grid has 2n(n − 1) edges, and the degree bound proves optimality.
- Zero distance: Exactly 14 of the 995 connected graphs on at most seven vertices have γ△ = 0, and all are regular circulants.Vanishing edit distance characterizes graphs already equal to an abelian Cayley graph.
7 Universal upper bounds and the extremal graph
Allowing deletions keeps normalized edit distance universally bounded, whereas additions-only completion can grow without bound. The star attains the maximum completion number, while random graphs show that the degree lower bound can miss most of the true difficulty.
- Universal bounds: γ△(G) ≤ 1 + n/(n −1) ≤ 3 for every connected G, and γ△(G) ≤ 2 for every non-tree.By contrast, γ+(K1,q) = (q −1)/2 →∞.
- Extremal graph: The star K1,n−1 attains the maximum γ+ among connected graphs on n vertices.The proof combines the universal upper bound with m ≥ n−1 and γ+(K1,n−1) = (n −2)/2.
- Extremal graph: Uniqueness of the star for γ+ is reduced to complement questions for non-star trees, while uniqueness for γ△ remains conjectural.The paper confirms both uniqueness claims only for connected graphs on at most seven vertices.
8 Hardness
Editing into a fixed cyclic host is NP-complete because the labeling problem encodes Hamiltonian Cycle. The cyclic formulation yields an exact path-partition expression, a polynomial matching-number relaxation, and an XP algorithm for bounded additive budgets, but fixed-parameter tractability remains open.
- Hardness: Deciding whether G can be edited into a fixed cyclic host Cn within budget B is NP-complete.The hardness persists even though the host group and connection set are specified in advance.
- Hardness: A labeling with k edges mapped to consecutive cyclic pairs has edit cost n + m − 2k, so optimization maximizes a spanning linear forest.The minimum cost is m − n + 2pmin(G), where pmin(G) is the path-partition number except that it is 0 for Hamiltonian graphs.
- Exact cyclic value: The exact cyclic-host value is governed by the path-partition number, and the problem remains NP-hard on planar cubic and bipartite graphs.Computing pp itself is NP-hard, so the exact characterization trades one hard optimization problem for another.
- Matching relaxation: The matching relaxation is polynomial-time computable and is tight on stars but loose on paths.On stars it gives (2q −3)/q; on even paths it gives 1 − 2/(n −1), versus the exact value 1/(n −1).
- Bounded edit budget: For fixed B, completing a graph to a circulant by adding at most B edges is solvable in polynomial time, placing the cyclic-host problem in XP.It is not known to be FPT because the exponent grows with B, and even the B = 0 recognition problem is unresolved in general.
9 The census
The census exhaustively evaluates 995 connected graphs, finding frequent strict separation between addition-only and edit invariants, while pooled rates are strongly dominated by seven-vertex graphs.
- Census methodology: Exact values were computed for all 995 connected graphs on 2 ≤ n ≤ 7 vertices, with certificates from exhaustive group, generating-set, and labeling searches.Translation normalization and class-count reductions make the computation exhaustive rather than heuristic.
- Invariant comparison: 84.7% of the census has γ△ < γ+, showing that deletions are usually beneficial and the two invariants should be reported separately.The edit-distance gap widens with n.
- Extremal graph: K1,6 uniquely maximizes γ△ at exactly 3/2 and is simultaneously extremal for completion in the census.The star’s extremality is attributed to its irregularity.
- Degree bound: 89.4% of census graphs attain the linear-time degree bound, which correlates with γ+ at Pearson r = 0.851 but is not a substitute for exact search.The bound is missed on 105 graphs and captures little difficulty on almost all graphs in the broader regime.
- Order effects: The pooled statistics are dominated by 853 graphs on seven vertices, while separation varies from 0% at n = 4 to 87.7% at n = 7.The order-stratified rates should therefore be preferred to pooled figures when describing general tendencies.
- Scope of the bound: The degree bound does not lower-bound γ△: the 4-regular disconnected graph C3 ∪ C4 has bound 0 but requires edits.Figure 1 consequently compares the bound with γ+, not γ△; the correlations are 0.851 and 0.741, respectively.
10 Conclusion and open problems
The paper closes by consolidating its complexity, structural, exact-family, and census results, then identifies open questions about extremality, recognition, random graphs, invariant agreement, and distortion.
- Conclusion: The paper establishes NP-hardness for the fixed-host problem, a linear-time degree lower bound with characterized equality, exact values for several families, and a certified seven-vertex census.It also proves that the star maximizes γ+ while γ△ has an absolute upper bound.
- Open problems: A remaining extremal question asks whether the star uniquely maximizes γ△, requiring complement matching or Hamiltonicity arguments for non-star trees.The corresponding γ△ statement is harder because its limiting star value agrees with the absolute bound.
- Open problems: The equality class of the degree bound is characterized algebraically but lacks a degree-sequence-level combinatorial test, whose complexity is also open.The condition is containment in a Δ-regular abelian Cayley host.
- Open problems: Parameterized complexity remains unresolved: Proposition 21 gives only XP, and the B = 0 case is abelian Cayley-graph recognition.The paper proposes settling recognition first.
- Open problems: Further questions concern γ+(G(n,p)) as p(n) → 0, the distinction among cubic graphs, agreement of γ+ and γ△, and distortion decay with host order.These problems extend the paper’s dense-random, census, invariant-comparison, and metric observations.
Data availability and reproducibility
The paper provides exact certificates for every graph through seven vertices and archives the code, certificates, and full census for reproducibility.
- Certification: Every n ≤ 7 value is certified by an explicit upper-bound witness and exhaustive lower-bound enumeration over abelian groups and symmetric connection sets.Values beyond seven vertices use the solver described in Appendix A.
- Availability: Code, certificates, and the full census are archived at doi:10.5281/zenodo.21852006, with graph labels following the Atlas of Graphs.
Declaration on the use of artificial intelligence
The authors disclose Claude’s use for software support and drafting assistance while retaining responsibility for the manuscript’s scientific content.
- Disclosure: Claude supported implementation, debugging, reproducibility, language, and editing, while the authors retained ownership of definitions, results, verification, direction, and conclusions.
A Solving beyond the exhaustive range
Beyond exhaustive enumeration, the paper uses local search over vertex labelings while exactly optimizing generating sets, and calibrates the heuristic against certified census optima. Plateau acceptance reduces mean cost per run without changing the best reachable value.
- Search method: The only heuristic component beyond the census range is the choice of vertex labeling; optimal generating sets remain computed exactly by enumeration.Local search is used because factorial enumeration becomes infeasible beyond the census.
- Calibration: 200 of 200 randomly sampled census graphs returned the certified optimum under four restarts and no instance-specific tuning.The authors state that this calibration provides no approximation guarantee.
- Acceptance: Equal-cost move acceptance matters because the cost landscape contains large isocost plateaus determined by class-count vectors.Strict descent can halt at the first plateau, whereas plateau descent can continue across equal-cost moves.
- Acceptance: With sufficient restarts, plateau and strict descent found the same best value on all three instances, while plateau descent reduced mean cost per run.The reported benefit is variance reduction rather than improved reachability or a better optimum.
- Standard graphs: For standard graphs, four cubic instances have edit count exactly n/2, forcing γ△=1/3, but Petersen and Desargues are explicit exceptions.The icosahedral graph also attains 1/3 despite being 5-regular, so the pattern is observational rather than structural.
B Distortion is a second, independent invariant
The paper separates edge-edit completion from metric fidelity: completion fixes the vertex set, whereas distortion evaluates embeddings into hosts of varying order. Stars and paths show that the two invariants can move in opposite directions and neither bounds the other.
- Definition: The bi-Lipschitz distortion c_N(G) is minimized over abelian hosts of order N≥n, symmetric generating sets, and injective embeddings.Unlike γ+ and γ△, c_N is defined for every host order N≥n.
- Definition: c_N(G)≥1 always, with equality exactly when G embeds isometrically into a host of order N.The least such host order is the invariant ν(G).
- Independence: On stars, γ+(K_1,q)=(q−1)/2 is unbounded while c_n(K_1,q)=2; on paths, γ+(P_n)=1/(n−1) tends to 0 while c_n(P_n) grows linearly.Therefore neither invariant bounds the other.
- Paths: A path needs only one added edge for completion, but closing it into a cycle makes its two endpoints adjacent and destroys the original metric.This is identified as a wraparound artefact of circular convolution.
- Frontier: For paths, the frontier formula is c_N(P_n)=(n−1)/(N−n+1) for n<N≤2n−2 under consecutive placement in Cay(Z_N,{±1}).The completion endpoint is N=n, while isometric embedding occurs at the larger frontier endpoint.