A criterion for the embeddability of \((r,q)\)-polycycles. (English. Russian original) Zbl 1045.05035

Russ. Math. Surv. 57, No. 3, 589-591 (2002); translation from Usp. Mat. Nauk 57, No. 3, 149-150 (2002).
An \((r,q)\)-polycycle is a plane graph all of whose inner faces are \(r\)-gons and all of whose inner vertices have degree \(q\). A graph is said to be \(\lambda\)-embeddable if it can be embedded into a hypercube so that the combinatorial distances between vertices get multiplied by \(\lambda\). The paper gives a necessary and sufficient condition for a \((3,5)\)-polycycle to be \(\lambda\)-embeddable. Definitions and prerequisites can be found in a paper by M.-M. Deza and M. Shtogrin [J. Geom. Phys. 40, 302–319 (2002; Zbl 0996.05081)].


05C10 Planar graphs; geometric and topological aspects of graph theory
05C12 Distance in graphs


Zbl 0996.05081
Full Text: DOI