Extremal and Nonextendible Polycycles

M. Deza ; M. I. Shtogrin

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

Résumé

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.