Analysis of Complex Networks

14.1 Introduction

Given q ∈ and R⊂ , a(R, q)polycycle P is a nonempty 2-connected map on a closed surface S with faces partitioned in two nonempty sets F₁ and F₂, so that:

(1) all elements of F₁ (called proper faces) are combinatorial i-gons with i ∈ R;

(2) all elements of F₂ (called holes) are pairwisely disjoint, that is, have no common vertices;

(3) all vertices have degree within {2,..., q} and all interior (i.e., not on the boundary of a hole) vertices are q-valent.

The map P can be finite or infinite and some of the faces of the set F₂ can be i-gons with i ∈ R or have a countable number of edges. In practice almost all the maps occurring here will be plane graphs, which most often will be finite plane graphs. Note that while any finite plane graph has a unique exterior face, an infinite plane graph can have any number of exterior faces, including 0 and infinity. The exterior faces will always be holes.

An isomorphism between two maps, G₁ and G₂, is a function φ mapping vertices, edges, and faces of G₁ to those of G₂ and preserving inclusion relations. Two (R, q)-polycycles, P₁ and P₂, are isomorphic if there is an isomorphism φ of corresponding plane graphs that maps the set of holes of P₁ to the set of holes of P₂. The automorphism group Aut(G) of a map G is the group of all ...