A quotient labeling theorem using Smith normal form produces certified isometric embeddings of any connected graph into abelian Cayley graphs, often far smaller than the hypercube baseline.
Ovchinnikov, Partial cubes: structures, characterizations, and con- structions, Discrete Math
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
math.CO 2years
2026 2verdicts
ACCEPT 2representative citing papers
Every connected graph embeds isometrically into an abelian Cayley host of order at least max(n, 2 diam), binary dimension at least max(diam, ceil(log2 n)), with exact values for stars and odd cycles and a census showing 57% of small graphs gain from non-binary hosts.
citing papers explorer
-
Minimal Isometric Embeddings of Graphs into Cayley Graphs of Finite Abelian Groups
A quotient labeling theorem using Smith normal form produces certified isometric embeddings of any connected graph into abelian Cayley graphs, often far smaller than the hypercube baseline.
-
Dimension and Order Bounds for Isometric Embeddings of Graphs into Abelian Cayley Graphs, and the Abelian Dividend
Every connected graph embeds isometrically into an abelian Cayley host of order at least max(n, 2 diam), binary dimension at least max(diam, ceil(log2 n)), with exact values for stars and odd cycles and a census showing 57% of small graphs gain from non-binary hosts.