Hamilton Cycles on McCauley Graphs

Suppose we wish to arrange a string of 8 bits in a circle such that every possible 3-bit string occurs exactly once.  One possible solution is 00011101, which (with wrap-around) gives the eight sequences of 3 bits

Each of the eight numbers in this sequence must be given by shifting the preceding number one bit to the left (i.e., multiplying by 2), adding either 0 or 1, and truncating the most significant bit (i.e., taking the residue modulo 8).  Thus, beginning with x=0, each succeeding number in the sequence is given by either 2x (mod 8) or 2x + 1 (mod 8).  We can express the above solution just in terms of the sequence of eight residues 0, 1, 3, 7, 6, 5, 2, 4.  There is only one other solution (up to rotations), namely, 0, 1, 2, 5, 3, 7, 6, 4, corresponding to the string 00010111.  These two solutions are just the reflections of each other (up to rotation).  Obviously the sequence of bits represents the summand b in the operation 2x + b (mod 8) at each step, and this is also the sequence of odd/even numbers in the result.

As noted by Joe McCauley, we can find analogous sequences modulo any even number n (not necessarily a power of 2), such that every residue modulo n appears exactly once, and each number is either 2x (mod n) or 2x + 1 (mod n) relative to the preceding number x. Of course, if n is not a power of 2, the evaluations modulo n will not be pure truncations, so these solutions don't correspond exactly to strings of binary bits taken k bits at a time as they do when n equals 2^k. Thus a more general representation is in terms of a directed graph consisting of n vertices numbered 0 to n-1, with a directed edge from each vertex j to the two vertices 2j and 2j + 1 (mod n). We will call this a McCauley graph, and consider the Hamilton cycles of these graphs. There are no Hamilton cycles for McCauley graphs of odd degree, so we need consider only the graphs for even values of n. The graphs for n = 2, 4, 6, 8, and 10 are shown below.

Each of these is a planar graph, meaning that it can be drawn on a two-dimensional surface with no crossing lines. (For clarity we haven’t shown the self-edges for the “0” and “n/2” vertices.) It’s easy to see that there is only one Hamilton cycle for each of the cases n = 2, 4, and 6. For the McCauley graph of degree n = 8 there are two distinct Hamilton cycles, as shown in the figures below.

For the McCauley graph of degree n = 10 there are three distinct Hamilton cycles, as shown in the figures below.

We also note that the graphs are symmetrical if we reduce the residues to the smallest signed residues modulo n-1. For the case n = 14 there are seven distinct Hamilton cycles, represented by the sequences of vertices listed below.

Reducing these to the smallest signed residues modulo 13 shows the symmetries more clearly.

The number of distinct Hamilton cycles for even values of n from 2 to 64 are listed below:

McCauley noted that the numbers of Hamilton cycles alternate between odd and even, i.e., the number is odd if and only if n/2 is odd. He asked if there are any other patterns in these numbers, and if there is any other way of producing them. It turns out that there is a nice “closed form” number-theoretic expression for these numbers. 

First we make a few more observations on the table. Letting H(n) denote the number of cycles of size n, we note that H(2(2n)) = 2^n-1H(2n) for all n. For example, H(36) = (256)H(18).  This takes care of H(n) for all n divisible by 4, so we need only determine the values of H(n) for n = 2k where k is odd.  Now we observe that if n = 2p for a prime p we usually have

Of course, by Fermat's theorem, we're assured this quantity is an integer for any prime p.  For example, H(2∙11) = (2¹⁰ – 1)/11 = 93. However, this doesn't cover the primes 7, 17, 23, or 31.  These are precisely the primes (in the range of the table) for which H(2p) is divisible by p itself.  Moreover, for each of these four primes the value of H(2p) is of the form pm² for some integer m. In other words, H(2p)/p is a square.  Furthermore, in three of these cases (p = 7, 17, and 23) we find that H(2p) = pm²  =  (2^p - 2)/(2p) - 2m, so we can solve for m = (2^(p-1)/2-1)/p, which implies

The only remaining prime case (in the table) is p = 31, for which we have h(2∙31) = 31⁵.  It’s also clear from the table that the values of h(2n) for odd composite n are related to divisors of 2^q - 1 for primes q that divide n.

To summarize these observations, let h(n) denote H(2n). We don't lose anything this way, since there are no cycles with odd lengths. With this convention, the observations mentioned above can be summarized as follows:

where ϕ(n) is Euler's totient function.  The prime 31 didn't fit into these patterns, but notice that we have

so we are led to suspect that h(p) for every prime p is of the form

for some divisor k of ϕ(p).  Furthermore, for each power of a prime, we apparently have

for a suitable divisor k of ϕ(p). Also, notice that for at least some odd primes p,q we have

where k again is a suitable divisor of ϕ(n). To this point we have left the value of “k” unspecified, other than to say it is a divisor of ϕ, but notice that for each integer N the suitable value of ϕ(N)/k is equal to the order of 2 modulo N. Letting ord(m,N) denote the least exponent s such that m^s – 1 is divisible by N, we have k = ϕ(N)/ord(2,N). This is consistent with the basic operation, which involves cycles generated by iterating x → 2x (or 2x+1) modulo N. Combining all these relations, we conjecture that, for any integer n = 2^rm where m is odd we have

Thus we arrive at an explicit formula for the number of distinct Hamilton cycles of McCauley graphs of degree n. (Note that 2nH(2n) could be regarded as the actual number of Hamilton cycles of degree 2n, because H(n) was restricted to those beginning with 0, each of which represents 2n others by rotation.) As an example, suppose we wish to determine the value of H(42), which equals h(21). In this case n = m = 21, which has the divisors 3, 7, and 21. Using the values ϕ(3) = 2, ϕ(7) = 6, ϕ(21) = 12, and ord(2,3) = 2, ord(2,7) = 3, ord(2,21) = 6, the preceding formula gives

in agreement with the table value of H(42).

Notice that h(n) is not a simple multiplicative function, because of the cross-product terms involving 2^ord(pq) – 1.  Still, it's an interesting definition based on the divisors.  (Can this can be inverted using something like the Mobius function?) This formula is valid for all the values in the table, which is fairly persuasive, but I haven’t proven that it gives h(n) for all n. Still, this is an interesting example of how much structure can be inferred (or at least guessed) about a combinatorial function strictly from examining its values, without even considering its definition.

The McCauley graphs are all planar up to n = 14, as shown by the figures below.

The first non-planar McCauley graph is for n = 16, shown in the figure below.

Incidentally, the sequence of integers h(n) is also the number (up to rotation) of n x n circulant invertible matrices over the field of integers modulo 2. A circulant matrix is one whose rows are all just rotated versions of a single row. For example, the following is a 4 x 4 circulant matrix:

A matrix is invertible if its determinant is non-zero. So, an invertible circulant matrix over the integers modulo 2 is a circulant matrix whose elements are either 0 or 1 and whose determinant is odd (i.e., congruent to 1 modulo 2). Since each row is just a rotated version of one of the rows, we can represent each such matrix (or rather the equivalence class of matrices up to rotation) by just the top row. The matrices for the first several values of n are indicated below.

We can generalize the above discussion to other moduli. For example, instead of considering all cycles of integers of length n such that each term s_k+1 is either 2s_k or 2s_k + 1 modulo n, we could allow each term to be of the form 3s_k, 3s_k + 1, or 3s_k + 2 modulo n.  For example, the four solutions (up to rotation) of length 8 are

Obviously each of these cycles is uniquely characterized by the sequence of "remainders" modulo 3, so they each correspond to an integer with those digits in base 3.  The numbers of cycles for n = 2 to 15 are listed below:

Recall that with base 2 there were no cycles except when n is divisible by 2. With base 3 there are clearly more cycles when n is divisible by 3 than when it is not, but there do exist cycles in the latter case.

Return to MathPages Main Menu