Metraipolis › archive › dc_0691597ffee4

Induced Embeddings of Graphs into Abelian Cayley Graphs — arXiv:2609.01486

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.01486
License (as archived)
CC0-1.0
Archived
2026-10-17T07:06:24.582Z
SHA-256 of the archived text
f1be905f0ff267b8a096290fe728b147cb45499ac857e7d754bd15fffb1f30d8
Stable URL of this page
https://metraipolis.com/documento/dc_0691597ffee4

How to cite

Induced Embeddings of Graphs into Abelian Cayley Graphs — arXiv:2609.01486 — arXiv (en), https://arxiv.org/abs/2609.01486 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0691597ffee4 (Metraipolis archive dc_0691597ffee4, sha256 f1be905f0ff267b8a096290fe728b147cb45499ac857e7d754bd15fffb1f30d8)
BibTeX
@misc{dc0691597ffee4,
  title = {Induced Embeddings of Graphs into Abelian Cayley Graphs — arXiv:2609.01486},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.01486},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0691597ffee4; sha256 f1be905f0ff267b8a096290fe728b147cb45499ac857e7d754bd15fffb1f30d8},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.01486. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For a finite graph $G$ on $n$ vertices, let $\eta(G)$ denote the least order of a finite abelian group $\Gamma$ for which $G$ is an induced subgraph of some Cayley graph of $\Gamma$. Babai and Sós (1985) settled the worst-case order of magnitude: it is $\Theta(n^2)$. We treat $\eta$ 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: $\eta(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 $\eta$ exactly for paths, where it equals $n+1$, and for complete bipartite graphs $K_{a,b}$, where it equals $2\max(a,b)$ and meets the floor. A Cartesian product bound gives $\eta(P_m \,\square\, P_m) = (1+o(1))n$. We report certified exact values of $\eta$ 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 $\eta$ exactly for the double stars $D_{q,q}$ with $2 \le q \le 6$, obtaining $5q$ in each case. Since $\eta(D_{6,6}) = 30$ exceeds $2n = 28$, no constant below $15/7$ can bound $\eta(T)/n$ over all trees.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-02 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.01486 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T06:52:59.697Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).