Geodesic
Extremal and Nonextendible Polycycles
Informatics and Automation, Discrete geometry and geometry of numbers, Tome 239 (2002), pp. 127-145.

Voir la notice de l'article provenant de la source Math-Net.Ru

We continue the study of $(r,q)$-polycycles, i.e. planar graphs $G$ that admit a realization on the plane such that all internal vertices have degree $q$, all boundary vertices have degree at most $q$, and all internal faces are combinatorial $r$-gons; moreover, the vertices, edges, and internal faces form a cell complex. Two extremal problems related to chemistry are solved: the description of $(r,q)$-polycycles with the maximal number of internal vertices for a given number of faces, and the description of nonextendible $(r,q)$-polycycles. Numerous examples of isohedral polycycles (whose symmetry groups are transitive on faces) are presented. The main proofs involve an abstract cell complex $\mathbf P(G)$ obtained from a planar realization of the graph $G$ by replacing all its internal faces by regular Euclidean $r$-gons. 
@article{TRSPY_2002_239_a8,
     author = {M. Deza and M. I. Shtogrin},
     title = {Extremal and {Nonextendible} {Polycycles}},
     journal = {Informatics and Automation},
     pages = {127--145},
     publisher = {mathdoc},
     volume = {239},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TRSPY_2002_239_a8/}
}
TY  - JOUR
AU  - M. Deza
AU  - M. I. Shtogrin
TI  - Extremal and Nonextendible Polycycles
JO  - Informatics and Automation
PY  - 2002
SP  - 127
EP  - 145
VL  - 239
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TRSPY_2002_239_a8/
LA  - ru
ID  - TRSPY_2002_239_a8
ER  - 
%0 Journal Article
%A M. Deza
%A M. I. Shtogrin
%T Extremal and Nonextendible Polycycles
%J Informatics and Automation
%D 2002
%P 127-145
%V 239
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TRSPY_2002_239_a8/
%G ru
%F TRSPY_2002_239_a8
M. Deza; M. I. Shtogrin. Extremal and Nonextendible Polycycles. Informatics and Automation, Discrete geometry and geometry of numbers, Tome 239 (2002), pp. 127-145. http://geodesic.mathdoc.fr/item/TRSPY_2002_239_a8/

[1] Deza M., Shtogrin M. I., “Vlozhenie khimicheskikh grafov v giperkuby”, Mat. zametki, 68:3 (2000), 339–352 | MR | Zbl

[2] Deza M., Shtogrin M., “Polycycles”, Voronoi Conf. on analitic number theory and space tilings, Abstracts (Kyiv, Sept. 7–14, 1998), Inst. Math. Nat. Acad. Sci. Ukraine, Kyiv, 1998, 19–23.

[3] Deza M., Shtogrin M. I., “Primitivnye politsikly i gelitseny”, UMN, 54:6 (1999), 159–160 | MR | Zbl

[4] Deza M., Shtogrin M. I., “Beskonechnye primitivnye politsikly”, UMN, 55:1 (2000), 179–180 | MR

[5] Shtogrin M. I., “Primitivnye politsikly: kriterii”, UMN, 54:6 (1999), 177–178 | MR | Zbl

[6] Shtogrin M. I., “Neprimitivnye politsikly i gelitseny”, UMN, 55:2 (2000), 155–156 | MR | Zbl

[7] Deza M., Shtogrin M. I., “Politsikly: simmetriya i vlozhimost”, UMN, 55:6 (2000), 129–130 | MR | Zbl

[8] Grünbaum B., Shephard G. C., Tilings and patterns, Freeman, New York, 1987 | MR | Zbl

[9] Bousquet-Mélou M., Guttman A. J., Orrick W. P., Rechnitzer A., “Inversion relations, reciprocity and polyominoes”, Ann. Comb., 3 (1999), 223–249 | DOI | MR | Zbl

[10] Cyvin S. J., Cyvin B. N., Brunvoll J., Bremdsdal E., Zhang Fuji, Guo Xiofeng, Tosic R., “Theory of polypentagons”, J. Chem. Inform. Comput. Sci., 33 (1993), 466–474 | DOI

[11] Harary F., Harborth H., “Extremal animals”, J. Comb., Inform. and Syst. Sci., 1 (1976), 1–8 | MR | Zbl

[12] Harborth H., “Some mosaic polyominoes”, Ars. Comb., 29 (1990), 5–12 | MR

[13] Aleksandrov A. D., Vypuklye mnogogranniki, Gostekhizdat, M., L., 1950 | MR

[14] Kharari F., Teoriya grafov, Mir, M., 1973 | MR

[15] Chepoi V., Deza M., Grishukhin V. P., “Clin d'oeil on $\ell_1$-embeddable planar graphs”, Discr. Appl. Math., 80 (1997), 3–19 | DOI | MR | Zbl

[16] Deza M., Shtogrin M. I., “Kriterii vlozhimosti $(r,q)$-politsiklov”, UMN, 57:3 (2002), 149–150 | MR | Zbl