Abstract
Cycles of various lengths composed of elements belonging to a set S can be used to define monocyclic permutations (“roundtable 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 NPcomplete 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 pairproperties 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 bruteforce 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.

View/download the openaccess fulltext PDF version
You can also download an
executable freeware utility NPC for Windows,
and its C++ sources.
Disclaimer: The NPC Utility has been checked for absence of any viruses.
In any case, the Author disclaims any responsability whatever related to its usage.
Please, cite this online document as:
Sykora S., On Neighbor Property Cycles,
Stan's Library, Vol.V, May 2014, DOI: 10.3247/SL5Math14.002 .
Discussions
Your comments are welcome and will appear here
