On Neighbor Property Cycles

Stanislav Sykora,

Extra Byte, Via R.Sanzio 22C, 20022 Castano Primo (MI), Italy,
in Stan's Library, Vol.V. First release 25 May 2014

Permalink:  DOI: 10.3247/SL5Math14.002

Other math articles in Stan's Library | Math Links Math Books | Stan's HUB

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.


View/download the open-access full-text 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

 

LEGAL MATTERS
Copyright ©2014 Stan's Library, ISSN 2421-1230, DOI: 10.3247/SL5Math14.002 Designed by Stan Sýkora