Induced Embeddings of Graphs into Abelian Cayley Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.01486
curl -X POST /api/v1/records/arxiv/2609.01486/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.01486/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'