Induced Embeddings of Graphs into Abelian Cayley Graphs
Abstract
For a finite graph G on n vertices, let η(G) denote the least order of a finite abelian group Γ for which G is an induced subgraph of some Cayley graph of Γ. Babai and Sós (1985) settled the worst-case order of magnitude: it is Θ(n2). We treat η instead as an invariant of the individual graph, minimised over all finite abelian groups rather than over the cyclic groups alone, which is the restriction implicit in the literature on representation numbers modulo n. We prove a local order floor: η(G) is at least the maximum of n and twice the largest independence number of a neighbourhood of G. This localises at an arbitrary vertex the correspondence of Babai and Sós between induced stars and sum-free sets; a corollary of the classification of maximum sum-free sets in abelian groups does not lower this floor, but restricts which host orders are admissible and so prunes the search. We determine η exactly for paths, where it equals n+1, and for complete bipartite graphs Ka,b, where it equals 2max(a,b) and meets the floor. A Cartesian product bound gives η(Pm □ Pm) = (1+o(1))n. We report certified exact values of η for $22$ graphs, computed over all abelian groups. Seventeen of the $22$ optimal hosts are cyclic, so on most of these graphs the cyclic restriction costs nothing; where it bites, however, it is expensive. A search restricted to cyclic groups returns $36$ for the Petersen graph against the true value $16$, and $59$ for the Frucht graph against $27$. The cost of the restriction is concentrated rather than diffuse, and we identify the graphs on which it is paid. We also determine η exactly for the double stars Dq,q with 2 ≤ q ≤ 6, obtaining 5q in each case. Since η(D6,6) = 30 exceeds 2n = 28, no constant below 15/7 can bound η(T)/n over all trees.
Related
- Cayley graphs of abelian groups, circular colorings and discrete fundamental groups
- Fast robbers on abelian Cayley graphs and digraphs
- Isomorphisms of abelian Cayley graphs with their natural edge-colouring
- Optimal Sparsifiers for Abelian Cayley Graphs
- Exact Diameter Windows for Random Cayley Graphs on Odd-Order Abelian Groups
BibTeX
@misc{souop2026induced,
title = {{Induced Embeddings of Graphs into Abelian Cayley Graphs}},
author = {Rigobert Fokam Souop and Laurent Bitjoka},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01486},
eprint = {2609.01486},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01486},
}
RIS
TY - UNPB
TI - Induced Embeddings of Graphs into Abelian Cayley Graphs
AU - Rigobert Fokam Souop
AU - Laurent Bitjoka
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.01486
UR - https://arxiv.org/abs/2609.01486
AB - For a finite graph G on n vertices, let η(G) denote the least order of a finite abelian group Γ for which G is an induced subgraph of some Cayley graph of Γ. Babai and Sós (1985) settled the worst-case order of magnitude: it is Θ(n^2). We treat η instead as an invariant of the individual graph, minimised over all finite abelian groups rather than over the cyclic groups alone, which is the restriction implicit in the literature on representation numbers modulo n. We prove a local order floor: η(G) is at least the maximum of n and twice the largest independence number of a neighbourhood of G. This localises at an arbitrary vertex the correspondence of Babai and Sós between induced stars and sum-free sets; a corollary of the classification of maximum sum-free sets in abelian groups does not lower this floor, but restricts which host orders are admissible and so prunes the search. We determine η exactly for paths, where it equals n+1, and for complete bipartite graphs K_a,b, where it equals 2max(a,b) and meets the floor. A Cartesian product bound gives η(P_m □ P_m) = (1+o(1))n. We report certified exact values of η for $22$ graphs, computed over all abelian groups. Seventeen of the $22$ optimal hosts are cyclic, so on most of these graphs the cyclic restriction costs nothing; where it bites, however, it is expensive. A search restricted to cyclic groups returns $36$ for the Petersen graph against the true value $16$, and $59$ for the Frucht graph against $27$. The cost of the restriction is concentrated rather than diffuse, and we identify the graphs on which it is paid. We also determine η exactly for the double stars D_q,q with 2 ≤ q ≤ 6, obtaining 5q in each case. Since η(D_6,6) = 30 exceeds 2n = 28, no constant below 15/7 can bound η(T)/n over all trees.
ER -