Clusters of cycles

A cluster of cycles (or (r,q)-polycycle) is a simple planar 2-connected finite or countable graph G of girth r and maximal vertex-degree q, which admits an (r,q)-polycyclic realization P(G) on the plane. An (r,q)-polycyclic realization is determined by the following properties: (i) all interior vertices are of degree q; (ii) all interior faces (denote their number by p_r) are combinatorial r-gons; (iii) all vertices, edges and interior faces form a cell-complex.An example of (r,q)-polycycle is the skeleton of (r^q), i.e. of the q-valent partition of the sphere, Euclidean plane or hyperbolic plane by regular r-gons. Call spheric pairs (r,q)=(3,3),(4,3),(3,4),(5,3),(3,5). Only for those five pairs, P((r^q)) is (r^q) without exterior face; otherwise, P((r^q))=(r^q).Here we give a compact survey of results on (r,q)-polycycles. We start with the following general results for any (r,q)-polycycle G: (i) P(G) is unique, except of (easy) case when G is the skeleton of one of the five Platonic polyhedra; (ii) P(G) admits a cell-homomorphism f into (r^q); (iii) a polynomial criterion to decide if given finite graph is a polycycle, is presented.Call a polycycle proper if it is a partial subgraph of (r^q) and a helicene, otherwise. In ARS Comb. A 29 (1990) 5], all proper spheric polycycles are given. An (r,q)-helicene exists if and only if p_r>(q−2)(r−1) and (r,q)≠(3,3). We list the (4,3)-, (3,4)-helicenes and the number of (5,3)-, (3,5)-helicenes for first interesting p_r. Any outerplanar (r,q)-polycycle G is a proper (r,2q−2)-polycycle and its projection f(P(G)) into (r^2q−2) is convex. Any outerplanar (3,q)-polycycle G is a proper (3,q+2)-polycycle.The symmetry group Aut(G) (equal to Aut(P(G)), except of Platonic case) of an (r,q)-polycycle G is a subgroup of Aut((r^q)) if it is proper and an extension of Aut(f(P(G))), otherwise. Aut(G) consists only of rotations and mirrors if G is finite, so its order divides one of the numbers 2r, 4 or 2q. Almost all polycycles G have trivial AutG.Call a polycycle G isotoxal (or isogonal, or isohedral) if AutG is transitive on edges (or vertices, or interior faces); use notation IT (or IG, or IH), for short. Only r-gons and non-spheric (r^q) are isotoxal. Let T^*(l,m,n) denote Coxeter’s triangle group of a triangle on S², E² or H² with angles π/l, π/m, π/n and let T(l,m,n) denote its subgroup of index 2, excluding motions of 2nd kind. We list all IG- or IH-polycycles for spheric (r,q) and construct many examples of IH-polycycles for general case (with AutG being above two groups for some parameters, including strip and modular groups). Any IG-, but not IT-polycycle is infinite, outerplanar and with same vertex-degree, we present two IG-, but not IH-polycycles with (r,q)=(3,5),(4,4) and AutG=T(2,3,∞)PSL(2,Z), T^*(2,4,∞). Any IH-polycycle has the same number of boundary edges for each its r-gon. For any r≥5, there exists a continuum of quasi-IH-polycycles, i.e. not isohedral, but all r-gons have the same 1-corona.On two notions of extremal polycycles:

1. We found for the spheric (r,q) the maximal number n_int of interior points for an (r,q)-polycycle with given p_r; in general case, (p_r/q)≤n_int<(rp_r/q) if any r-gon contains an interior point.

2. All non-extendible (r,q)-polycycles (i.e. not a proper subgraph of another (r,q)-polycycle) are (r^q), four special ones, (possibly, but we conjecture their non-existence) some other finite (3,5)-polycycles, and, for any (r,q)≠(3,3),(3,4),(4,3), a continuum of infinite ones.

On isometric embedding of polycycles into hypercubes Q_m, half-hypercubes and, if infinite, into cubic lattices Z_m, : for (r,q)≠(5,3),(3,5), there are exactly three non-embeddable polycycles (including (4³)−e, (3⁴)−e); all non-embeddable (5,3)-polycycles are characterized by two forbidden sub-polycycles with p₅=6.