Analysis of Complex Networks

14

Elementary Elliptic (R, q)-Polycycles

Michel Deza, Mathieu Dutour Sikirić, and Mikhail Shtogrin

A(R, q)-polycycle is a map whose faces, besides some disjoint holes, are i-gons, i ∈ R, and whose vertices have a degree between 2 and q with vertices outside of holes being q-valent. This notion arises in organic chemistry and crystallography as well as in purely mathematical contexts.

A(R, q)-polycycle is called elementary if it cannot be cut along an edge. Every (R, q)-polycycle can be uniquely decomposed into elementary ones. This decomposition is useful for computer enumeration and determination of classes of plane graphs and (R, q)-polycycles [6, 11–14, 17, 20]. A critical step for using the decomposition theorem is to be able to list all elementary polycycles occurring in a given problem.

A(R, q)-polycycle is called elliptic, parabolic, or hyperbolic if (where r = max_{i ∈R}i) is positive, zero, or negative, respectively). Here we determine all elementary elliptic (R, q)-polycycles. For parabolic and hyperbolic cases, there is a continuum of possibilities, so this method is less useful.