5 - Polycycles with given boundary

Summary

The (r, q)-boundary sequence of a finite (r, q)-polycycle P is the sequence b(P) of numbers enumerating, up to a cyclic shift or reversal, the consecutive degrees of vertices incident to the exterior face. For earlier applications of this (and other) codes, see.

Given an (r, q)-boundary sequence b, a plane graph P is called a (r, q)-filling of b if P is an (r, q)-polycycle such that b = b(P).

In this chapter we consider the unicity of those (r, q)-fillings and algorithms used for their computations.

The problem of uniqueness of (r, q)-fillings

By inspecting the list of (r, q)-polycycles for (r, q) = (3, 3), (3, 4), or (4, 3) in Section 4.2, we find that the (r, q)-boundary sequence of an (r, q)-polycycle determines it uniquely. We expect that for any other pair (r, q) this is not so

We show that the value r = 3, 4 are the only ones, such that the (r, 3)-boundary sequence always defines its (r, 3)-filling uniquely. Note that an (r, q)-polycycle, which is not an unique filling of its boundary, is, necessarily, a helicene. Some examples of non-uniqueness of (r, 3)-fillings are cases of boundaries b, admitting an (r, 3)-filling P with the symmetry group of b being larger than the symmetry group of P, implying the existence of several different (r, 3)-fillings.