Abstract

Cycles of various lengths composed of elements belonging to a set S can be used to define monocyclic permutations (“round-table seatings”) of subsets of S. Those are interesting by themselves, but the whole context becomes still more interesting when the elements possess specific properties or when pairs of elements of S have a specific property (implying a partition of the product set SxS). In this case, for example, one can construct cycles in which every pair of adjacent elements (neighbors) has, or has not, a specific property. For cycle lengths greater than 2, this reduces to finding all distinct Hamiltonian cycles (an NP-complete problem) in a simple graph in which the vertices correspond to the elements of the cycle, and an edge between two vertices is present only if the pair possesses the property.

This essay uses many selected cases to illustrate some of the counting tasks and problems that arise in these situations, using cycles of integer numbers. The pair-properties P(i,j) considered here are: i,j differ by exactly one bit in their binary expansions (Gray property), or by some minimum amount, or by a power of 2 or 3, or by a prime, or they are coprime, or their difference and/or sum are primes, etc.

This study is an extension of the earlier one [1] on canonical Gray cycles (CGC), since the CGCs are a special case of NPC’s. In both studies, a rather brute-force algorithm was used to enumerate/list all the NPC’s with any given property, while a more efficient algorithm is being developed. The included C++ code is easily adaptable to tackle all problems of this type but, alas, it has severe execution time limits for large cycle lengths.