Analysis of Complex Networks

14.2 Kernel Elementary Polycycles

Call kernel Ker(P) of an(R, q)_simp-polycycle P the cell complex formed by its vertices, edge, and faces that do not contain a boundary vertex. Call an (R, q) polycycle kernel-elementary if it is an r-gon or if it has a nonempty connected kernel such that the deletion of any face from the kernel will diminish it (i.e., any face of the polycycle is incident to its kernel).

Theorem 14.2

(i) If an (R, q)_simp-polycycle is kernel-elementary, then it is elementary.

(ii) If (R, q) is elliptic, then any elementary (R, q)_simp-polycycle is also kernelelementary.

Proof. (i) Take a kernel-elementary (R, q)-polycycle P; one can assume it to be different from an r-gon. Let P₁,..., P_m be the elementary components of this polycycle. The connectedness condition on the kernel gives that all P_i but one are r-gons with r ∈ R. But removing the components P_i that are r-gons does not change the kernel; thus, m =1and P is elementary.

(ii) Consider any two vertices of an r-gon of an elliptic (R, q)-polycycle that belongs to the kernel of this polycycle. The shortest edge path between these vertices lies inside the union of two stars of r-gons with the centers at these two vertices; this result can easily be verified in each particular case for any elliptic parameters (R, q) = ({2, 3, 4, 5},3), ({2, 3},4), and ({2, 3},5). Hence, any r-gon of an elliptic (R, q)-polycycle is incident with only one simply connected component of its kernel. All r-gons that are incident with ...