Bent Hamilton Cycles in d-Dimensional Grid Graphs

F. Ruskey ^{∗}  Joe Sawada ^{†}

May 15, 2002

Abstract

A bent Hamilton cycle in a grid graph is one in which each edge in a successive pair of edges lies in a different dimension. We show that the d-dimensional grid graph has a bent Hamilton cycle if some dimension is even and d ≥ 3, and does not have a bent Hamilton cycle if all dimensions are odd. In the latter case, we determine the conditions for when a bent Hamilton path exists. For the d-dimensional toroidal grid graph (i.e., the graph product of d cycles), we show that there exists a bent Hamilton cycle when all dimensions are odd and d ≥ 3. We also show that if d = 2, then there exists a bent Hamilton cycle if and only if both dimensions are even.

Keywords: Grid graph, Hamilton cycle, Hamilton path, Gray code.

AMS subject classification: 05C45

1 Introduction

The figure below shows two incarnations of a popular “snake” puzzle. The figure represents a flattened view of a series of 27 unit cubes that are held together by a shock cord running from one end to the other. The cubes can rotate at those faces that are held together by the cord. The object of the puzzle is to arrange the snake into a 3 × 3 × 3 cube.

∗Department of Computer Science, University of Victoria, Canada. Research supported by NSERC.

†Department of Computer Science, University of Toronto, Canada . Research supported by an NSERC postdoctoral fellowship.

submitted to the electronic journal of combinatorics 1

If each cube is regarded as the vertex of a graph, then the problem amounts to finding a certain restricted Hamilton path in a 3 × 3 × 3 grid graph, a natural generalization of the 3-dimensional hypercube.

In a uniform version of the puzzle, the snake would consist entirely of zig-zags, as shown above. This version is not solvable for 3 × 3 × 3, but it does inspire the following definition. Let G be a graph and let f : E(G) → C be a “coloring” of the edges of G. A cycle or path in G is said to be bent with respect to f if successive pairs of edges get different colors; i.e., if v_{1}, v_{2}, …, v_{n} is the path or cycle then

f(v_{i−1}, v_{i}) ≠ f(v_{i}, v_{i+1})

for all i, indices taken circularly for cycles.

There are several natural scenarios in which we might consider bent Hamilton cycles. If G is a Cayley graph then its edges are naturally colored by the generators and the existence of a bent Hamilton cycle for that coloring corresponds to a sequence of generators where no generator occurs twice in a row.

If G is the Cartesian product of smaller graphs, say G = G_{1} × G_{2} × ⋯ × G_{d}, then a natural coloring of an edge of G is the index i of the graph G_{i} from which the edge arises. In this paper we will be particularly concerned with the cases where each G_{i} is a path or each G_{i} is a cycle.

Definition 1 The grid graph Q(n_{1}, n_{2}, …, n_{d}) is the graph P_{n_{1}} × P_{n_{2}} × ⋯ × P_{n_{d}} where P_{m} is a path of m vertices.

Definition 2 The toroidal grid graph Q′(n_{1}, n_{2}, …, n_{d}) is the graph C_{n_{1}}×C_{n_{2}}×⋯×C_{n_{d}} where C_{m} is a cycle of m vertices.

Clearly Q(n_{1}, n_{2}, …, n_{d}) is a spanning subgraph of Q′(n_{1}, n_{2}, …, n_{d}). Those edges of Q′ that are not present in Q will be referred to as wrapped edges. The toroidal grid graph is an example of a Cayley graph over an Abelian group.

We take the vertex set of Q(n_{1}, n_{2}, …, n_{d}) to be

{(x_{1}, x_{2}, …, x_{d}) | 0 ≤ x_{i} < n_{i}},

with edges joining those vertices (x_{1}, …, x_{d}) and (y_{1}, …, y_{d}) for which

∑_{i=1}^{d} |x_{i} − y_{i}| = 1.  (1)

In other words, edges join vertices that differ by 1 in one component. As special cases, Q(n_{1}, n_{2}) is the usual n_{1} by n_{2} two-dimensional grid graph and Q(2, 2, …, 2) is the hypercube Q_{d}.

Any Hamilton path in the hypercube has the property that the coordinate that changes in successive edges is different; for example, in the famous binary reflected Gray code the successive dimensions are given by the well-known sequence 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,... The Hamilton paths that are usually constructed in d-dimensional grid graphs do not have this property; they use some dimension many times in a row. Here we examine those Hamilton paths and cycles that change dimension at every pair of successive edges; such paths are said to be bent.

Throughout this paper we will assume that each n_{i} ≥ 2. First we consider d ≥ 3 and prove in Section 2 that there exists a bent Hamilton cycle in Q(n_{1}, n_{2}, …, n_{d}) whenever some n_{i} is even. If all n_{i} are odd, then because the graph is bipartite with an odd number of vertices, there is no (bent) Hamilton cycle. As a result, we consider the following two problems when all n_{i} are odd:

(1) Does there exist a bent Hamilton cycle in Q′(n_{1}, n_{2}, …, n_{d}) for d ≥ 3?

(2) Does there exist a bent Hamilton path in Q(n_{1}, n_{2}, …, n_{d}) for d ≥ 3?

In Section 3, we prove that the answer to the first problem is always yes. In Section 4, we prove that the answer to the second problem is always yes as long as the grid is not of the form Q(3, 3, odd) or Q(3, 5, 5), with the Q(3, 5, 5) case remaining unsettled. In Section 5 we consider the 2 dimensional case, proving that a bent Hamilton cycle exists in Q′(n, m) if and only if both n and m are even.

Our results fall within the area of combinatorial Gray codes (for an excellent survey, see Savage [5]). In general, it is a simple matter to find Hamilton paths and cycles in d-dimensional grids. There are not many papers that have considered restricted types of Hamilton paths and cycles in grids; one that does is the paper of Trotter and Erdös [6] about the existence of Hamilton cycles in the direct product of two directed cycles. Itai, Papadimitriou, and Szwarcfiter [3] determine necessary and sufficient conditions for a two-dimensional grid to have a Hamilton path between two specified vertices.

2 Existence of bent Hamilton cycles

In this section we give constructive proofs for the existence of bent Hamilton cycles in Q(n_{1}, n_{2}, …, n_{d}) when d ≥ 3 and at least one dimension is even. As mentioned earlier, no such cycle exists if all dimensions are odd. When d = 2, a bent Hamilton cycle exists in Q(n, m) if and only if n = m = 2. We investigate the 2-dimensional case more thoroughly in Section 5.

Our general strategy for constructing a bent Hamilton cycle in Q(n_{1}, n_{2}, …, n_{d}) is to first deal with the case Q(n, m, 2). By carefully choosing the cycle, we can extend it to Q(n, m, 2k), and then to higher dimensions.

First, we illustrate bent Hamilton cycles for the three exceptional cases of Q(4, 2, 2), Q(3, 2, 2), and Q(3, 3, 2) in Figure 1. Now let us consider the general case of Q(n, m, 2) as consisting of a vertical dimension, a horizontal dimension, and two layers, top and bottom. An edge in a bent Hamilton cycle H in a three dimensional grid graph is said Figure 1: Bent Hamilton cycles in Q(4, 2, 2), Q(3, 2, 2), and Q(3, 3, 2) respectively.

w  ^{v}^{u}^{x}  (b) (a)

Figure 2: (a) A joinable pair of edges; (b) The extension of a Q(3, 3, 2) to Q(3, 3, 6) using joinable edges.

to be joinable if it lies on an outer face and both of its neighboring edges also lie on the same outer face. A joinable pair of edges is two joinable edges lying on opposite faces, and in the same relative position on the two faces.

Consider a Hamilton cycle in Q(n, m, 2) that contains a joinable pair {(u, v), (w, x)}. We can repeatedly join such graphs together to obtain a bent Hamilton cycle in Q(n, m, 2k) by removing the edges (u, v) and (w′, x′) and by adding the edges (u, w′) and (v, x′) between successive graphs. As an example, Figure 2(a) shows a bent Hamilton cycle in Q(3, 3, 2) along with the joinable edges (drawn red and thicker); this cycle has one other joinable pair. Figure 2(b) shows how the joinable edges can be used to find a bent Hamilton cycle in Q(3, 3, 6). From this illustrative example the reader should be convinced that it is possible to construct a bent Hamilton cycle in Q(n, m, 2k) from a bent Hamilton cycle in Q(n, m, 2) that has a joinable pair of edges.

We now show the constructions for these special bent Hamilton cycles in Q(n, m, 2). Three cases are considered which majorize the exceptional cases: Figure 3 illustrates the case when n and m are both even; Figure 4 illustrates the case when n is even and m is odd; Figure 5 illustrates the case when n and m are both odd. Each figure shows a bent

u  v w  x  u  v w  x BOTTOM LAYER  TOP LAYER BOTTOM LAYER TOP LAYER

Figure 3: Bent Hamilton cycles in Q(2s, 2t, 2), with t, s ≥ 2.

Hamilton cycle as viewed by the top and bottom layers. The joinable pairs are drawn thicker. In each case, a base case is shown along with an illustration of how the cycle gets extended when n and m are incremented by 2, with the red edges giving the extension. In each case the constructions can be extended by other even amounts by using the same extension pattern used to extend by 2. These constructions along with the exceptional cases prove the following lemma.

Lemma 1 There exists a bent Hamilton cycle in Q(n, m, 2k) for all n, m ≥ 2 and k ≥ 1.

The following dimension extending lemma shows how we can construct a bent Hamilton cycle in Q(n_{1}, n_{2}, …, n_{d}, m) from a bent Hamilton cycle in Q(n_{1}, n_{2}, …, n_{d}).

Lemma 2 If there is a bent Hamilton cycle in Q(n_{1}, n_{2}, …, n_{d}), then there is a bent Hamilton cycle in Q(n_{1}, n_{2}, …, n_{d}, m).

Proof: Let C be a bent Hamilton cycle in Q(n_{1}, n_{2}, …, n_{d}) containing the non-adjacent edges (u, v) and (w, x). We construct a bent Hamilton cycle in Q(n_{1}, n_{2}, …, n_{d}, m) by using the cycle C in each of m copies of Q(n_{1}, n_{2}, …, n_{d}), labeled Q_{1}, Q_{2}, …, Q_{m} respectively, and performing the following m − 1 operations. For each odd i from 1 to m − 1 we remove the edge (u_{i}, v_{i}) from Q_{i} and (u_{i+1}, v_{i+1}) from Q_{i+1} and add the edges (u_{i}, u_{i+1}) and (v_{i}, v_{i+1}). For each even i from 1 to m − 1 we remove the edge (w_{i}, x_{i}) from Q_{i} and (w_{i+1}, x_{i+1}) from Q_{i+1} and add the edges (w_{i}, w_{i+1}) and (x_{i}, x_{i+1}). The result is a bent Hamilton cycle in Q(n_{1}, n_{2}, …, n_{d}, m). □

In Figure 6 we illustrate the proof by showing how a bent Hamilton cycle in Q(2, 2, 2) can be used to obtain a bent Hamilton cycle in Q(2, 2, 2, 4). An identical proof can be used to prove the following corollary.

u  v w  x  w  x v u TOP LAYER BOTTOM LAYER  TOP LAYER BOTTOM LAYER

Figure 4: Bent Hamilton cycles in Q(2s, 2t − 1, 2), with t, s ≥ 2.

u  v w  x  u  v w  x TOP LAYER  BOTTOM LAYER BOTTOM LAYER  TOP LAYER

Figure 5: Bent Hamilton cycles in Q(2s + 1, 2t − 1, 2), with t, s ≥ 2.

submitted to the electronic journal of combinatorics 6

v_{1}^{u_{1}} ^{x_{1}}^{w_{1}}  ^{v_{2}}  ^{v_{3}}  ^{v_{4}} Q_{2}  Q_{3}  Q_{4} Q_{1}

Figure 6: Using a bent Hamilton cycle in Q(2, 2, 2) to obtain bent Hamilton cycle in Q(2, 2, 2, 4).

Corollary 1 If there is a bent Hamilton cycle in Q′(n_{1}, n_{2}, …, n_{d}), then there is a bent Hamilton cycle in Q′(n_{1}, n_{2}, …, n_{d}, m).

Combining Lemma 1 with Lemma 2 we arrive at the following theorem.

Theorem 1 If d ≥ 3 and at least one n_{i} is even then Q(n_{1}, n_{2}, …, n_{d}) has a bent Hamilton cycle.

3 Bent Hamilton cycles in odd toroidal grid graphs

In the previous section we detailed constructions for finding a bent Hamilton cycle in the graph Q(n_{1}, n_{2}, …, n_{d}) for d ≥ 3, where at least one of the n_{i} is even. We have also shown that if all n_{i} are odd, there exists no bent Hamilton cycle. In this section, we consider the graph Q′(n_{1}, n_{2}, …, n_{d}) and construct a bent Hamilton cycle when all n_{i} are odd.

Following the construction in the previous section, we first construct a bent Hamilton cycle in Q′(3, 3, 3) and then add additional pieces to increase the value for some dimension by 2 — thus constructing a bent Hamilton cycle in all Q′(odd, odd, odd). We then use Corollary 1 to expand to higher dimensions.

An exhaustive search reveals that there are exactly nine non-isomorphic Hamilton cycles in Q′(3, 3, 3). We specify each cycle as a circular string over the alphabet F,B,U,D,L,R, each letter standing for one of the directions forward, backward, up, down, left, or right. The lexicographically least representative of each equivalence class is as follows:

    BDBLBDBRBDRBDLDRBDRDLBDRDBR  BDBLBDBRBDRDBLDRDBRDLDBRDBR
    BDBLBDRBLBDBLUBURULBLURUBLU  BDBLBDRBRURDBDRURBDRBLBDBLU
    BDBLBDBRFRDRFURDRFRDLDBUBLU  BDBLBDBULBUBDLDRFRDRUFRDRFR
    BDBLBDFDRURFDRFLFDFRDRFRULU  BDBLBDLFLDLUFULBUBDLDBRDRFR

    BDBLFLURUBDBLFLURUBDBLFLURU

We will use the final cycle shown on this list. It possesses a rather pretty 3-fold periodic symmetry: (BDB-LFL-URU)^{3}. It is illustrated in the lower left of Figure 7. The red arrows indicate wrapped edges.

For our construction, imagine starting with a toroidal grid G with a bent Hamilton cycle H and adding a piece P, that is also a toroidal grid, with compatible dimensions. We can extend H to a bent Hamilton cycle H′ in the toroidal grid G + P if the following conditions on P are met. Suppose that there are w wrapped edges along the dimension of joining. Then P must contain w disjoint cycles that partition the vertices of P. Each of these w cycles must contain a wrapped edge in P along the joining dimension. Further, they must lie in the same relative position as the w wrapped edges in G.

For example, consider the toroidal grid graph G = Q′(3, 3, 3) shown in the lower left of Figure 7 along with a corresponding bent Hamilton cycle H. Let P = Q′(2, 3, 3) be the toroidal grid shown at the lower right in Figure 7. In this example, G has w = 3 wrapped edges in the joining dimension (dimension 1), as does the collection of 3 cycles that partition P. Further, those three wrapped edges lie in the same relative positions in both P and G.

Since the conditions on P are satisfied, we can extend H to create a bent Hamilton cycle in G + P. In general, this can be done by removing the w corresponding wrapped edges in each of G and P and replacing them with w non-wrapped edges that extend across the joining dimension of G + P and with w wrapped edges from G to P. This description is a bit vague, but the idea can be seen by looking at the example. From our example, we join each of the wrapped endpoints of G and P (the red arrows) that point towards each other to create w new non-wrapped edges across the joining dimension. Similarly, we join the endpoints with red arrows pointing away from each other to create the new wrapped edges in G + P. We thus obtain a bent Hamilton cycle in Q′(5, 3, 3), and by repeatedly joining P an appropriate number of times, a bent Hamilton cycle for any Q′(odd, 3, 3).

Observe that the Q′(3, 2, 3) shown in the upper left hand corner of Figure 7 also has a partition into 3 bent cycles and that the wrapped edges match along the joining dimension, dimension 2 in this case. Also, by joining the Q′(2, 2, 3) shown in the upper right corner, we have a partition of Q′(odd, 2, 3) into 3 bent cycles with no new wrapped edges introduced in dimension 2. We can thus add the Q′(odd, 2, 3) piece to the previously constructed Q′(odd, 3, 3) piece to get a bent Hamilton cycle in Q′(odd, 5, 3), and successively in any Q′(odd, odd, 3).

Finally, using a similar process again, we can add a piece like the ones showed in Figure 8 to the corresponding Q′(odd, odd, 3) to obtain a bent Hamilton cycle in Q′(odd, odd, odd).

Theorem 2 If d ≥ 3, then there is a bent Hamilton cycle in Q′(n_{1}, n_{2}, …, n_{d}).

4 Bent Hamilton paths in odd grids

We have already seen that there is no bent Hamilton cycle in Q(n_{1}, n_{2}, …, n_{d}) if all dimensions are odd. In this section we consider the problem of finding bent Hamilton paths in Q(n_{1}, n_{2}, …, n_{d}) when all n_{i} are odd. If d = 2, then the results of the following section show that there is no bent Hamilton path unless n_{1} ≤ 2 or n_{2} ≤ 2. But what about larger values of d? First we consider 3 dimensions.

Figure 7: A bent Hamilton cycle in Q′(3, 3, 3) with extentions showing a bent Hamilton cycle in Q′(odd, odd, 3).

Figure 8: An illustration of two (odd, odd, 2) extension pieces used to construct a bent Hamilton cycle in Q′(odd, odd, odd).

Theorem 3 There is no bent Hamilton path in Q(3, 3, 2k + 1), for any k ≥ 1.

Proof: Let m = 2k + 1. Assume that there is a bent Hamilton path P in Q(3, 3, m). Call the four paths induced by the 4m vertices of the form (1, 1, z), (1, 3, z), (3, 1, z), and (3, 3, z) the spines of the graph. Consider the sum S of the degrees in P of the vertices along the spines. Since P can contain at most k edges from each spine, the spines contribute at most 8k to S. Furthermore, along each of the m planes of the form (x, y, j) for fixed j ∈ {1, 2, ..., m}, the path P can contain at most 4 edges incident to vertices on the spines, because P is bent. Thus these edges can contribute at most 4m to S. Thus in total, S is bounded above by 8k + 4(2k + 1) = 16k + 4. However, since any path has at most two vertices of degree less than two, any subset of size 4m of its vertices must have degree sum at least 2(4m − 2) + 2 = 2(4(2k + 1) − 2) + 2 = 2(8k + 2) + 2 = 16k + 6. Contradiction. □

We now investigate the situation when two or more of the odd dimensions are greater than or equal to 5. We consider 3 cases: Q(3, 5, 5), Q(5, 5, 5), and the rest. In the first case of Q(3, 5, 5) we tried using an exhaustive search to show that there is no bent Hamilton path, but the computation has not yet finished.

Conjecture 1 There is no bent Hamilton path in Q(3, 5, 5).

For Q(5, 5, 5) we illustrate a bent Hamilton path in Figure 9. In this figure we show bent covers for each of the 5 successive levels. If there is an endpoint of a path in level i that has a surrounding circle, then there is an edge going from this endpoint to the corresponding endpoint in level i − 1. Similarly, if an endpoint in level i has no surrounding circle then there is an edge going from such an endpoint to a corresponding endpoint in level i + 1. The start/end points of the bent Hamilton path are indicated by the 2 squares.

For the rest of Q(odd, odd, odd) where at least two of the dimensions are greater than or equal to 5, we can construct a bent Hamilton path using the one illustrated for Q(3, 5, 7) in Figure 10 as the basis. In this figure, we show joinable edges x−x, y −y and z −z. For each of these edges, we can join the graphs Q(odd, odd, 2) outlined in Figure 5 to obtain a bent Hamilton path in a larger graph. Such additions must be done in order of x, y, z.

Theorem 4 There exists a bent Hamilton path in Q(odd, odd, odd), where at least two dimensions are greater than or equal to 5 and not including Q(3, 5, 5).

We can extend any Hamilton path in Q(n_{1}, n_{2}, n_{3}) to Q(n_{1}, n_{2}, n_{3}, n_{4}) by making n_{4} copies of the bent Hamilton path Q_{1}, Q_{2}, …, Q_{n_{4}} and joining the endpoint of Q_{i} to the startpoint of Q_{i+1} for i = 1, 2, …, n_{4} − 1. Similarly we can extend to higher dimensions.

Since there are no bent Hamilton paths in Q(3, 3, 5) or Q(3, 5, 5), we still need to show that there exists bent Hamilton paths Q(3, 3, 3, odd) and Q(3, 3, 5, 5) to prove the following theorem.

Theorem 5 If d ≥ 4 then there is a bent Hamilton path in Q(n_{1}, n_{2}, …, n_{d}), where all n_{i} are odd.

Figure 9: Bent Hamilton path in Q(5, 5, 5).

submitted to the electronic journal of combinatorics 11

y  ^{z}  ^{z} Level 1  Level 2  Level 3^{y}  ^{x}^{x}

Figure 10: Bent Hamilton path in Q(3, 5, 7).

To find bent Hamilton paths in the two anomalous cases, we use two dimensions to view four dimensions. Our basic strategy is to view Q(n_{1}, n_{2}, n_{3}, n_{4}) as Q(n_{1}, n_{2}) × Q(n_{3}, n_{4}). In particular, we find Hamilton paths in Q(n_{1}, n_{2}) and Q(n_{3}, n_{4}) that are not bent, but which can be spliced together in a certain way to yield a bent Hamilton path in the product. Using this strategy, we show constructions of bent Hamilton paths in Q(3, 3, 3, 3), Q(3, 3, 3, m) for all odd m > 3, and Q(3, 3, 5, 5) — thus proving the theorem. A similar strategy was employed in [1] for the construction of restricted Gray codes.

Figure 11 shows two Hamilton paths in Q(3, 3) that can be encoded 2^{+}2^{+}1^{+}1^{+}2^{−}1^{−}2^{−}1^{+} and 1^{+}2^{+}1^{−}2^{+}1^{+}1^{+}2^{−}2^{−} respectively. A 1 indicates a move horizontally, where the superscript ‘+’ indicates a move right and the superscipt ‘−’ indicates a move left. A 2 indicates a move vertically, where the superscript ‘+’ indicates a move up and the superscipt ‘−’ indicates a move down. This figure also shows a Hamilton path in Q(3, 5), and indicates how that path can be extended into one in Q(3, m), for all odd m > 3. The key to these (latter) specific paths is that the first 2 values in the paths alternate as well as the last 3.

Now consider the grid graph Q(n_{1}·n_{2}, n_{3}·n_{4}). We will label the horizontal and vertical directions using the appropriate Hamilton paths shown from Figure 11. For example, Figure 12 shows a Hamilton path in Q(3·3, 3·3) where the rows and columns have been labeled by the encoding used for the Hamilton path in Q(3, 3) shown in Figure 11(a). Dimensions 1 and 2 are used on the horizontal axis and dimensions 3 and 4 are used on the vertical axis. To obtain a bent Hamilton path in Q(3, 3, 3, 3) starting from (0,0,0,0), we trace the Hamilton path in Q(9, 9) starting from the bottom left corner (0,0), and read off the label in the corresponding row or column, depending on whether a vertical or a horizontal move is made. If the direction is down or to the left then the superscript of the corresponding value must be changed. Thus, the resulting transition sequence of the bent Hamilton path in Q(3, 3, 3, 3) begins with 4^{+}2^{+}4^{−}2^{+}4^{+}1^{+}4^{−}1^{+}4^{+}2^{−}4^{−}1^{−}2^{−}1^{+}4^{+}1^{−}2^{+}4^{+} …

Using the same methodology we can construct bent Hamilton paths for the remaining two cases. A Hamilton path for Q(3 · 3, 3 · 5) that can be used to obtain a bent Hamil-

1^{+}2^{+}1^{−}2^{+}1^{+}1^{+}2^{−}2^{−} 2^{+}2^{+}1^{+}1^{+}2^{−}1^{−}2^{−}1^{+} 1^{+}2^{+}1^{−}2^{+}1^{+}1^{+}1^{+}1^{+}2^{−}2^{−}1^{−}2^{+}1^{−}2^{−} 1^{+}2^{+} ⋯ 2^{+}1^{−}2^{−} 1^{+}2^{+} ⋯ 2^{+}1^{−}2^{−} Q(3, 3) (a) Q(3, 3) (b) Q(3, 5) Q(3, 7) Q(3, 9)

Figure 11: Special Hamilton paths in Q(3, 3) and Q(3, odd).

ton path in Q(3, 3, 3, 5) is illustrated in Figure 13. In this case, the Hamilton path for Q(3, 3)(b) is used to label the vertical axis. Notice that the middle values (the *’s) of the 3 by 5 sequence on the horizontal axis are not important since there are no two successive horizontal edges in a *-ed column. Therefore, a Hamilton path can be created in a similar fashion for Q(3 · 3, 3 · m) where m is an odd number greater than or equal to 5. Finally we show a Hamilton path construction for Q(3 · 5, 3 · 5) in Figure 14 which yields a bent Hamilton path in Q(3, 3, 5, 5).

5 The case of 2 dimensions

In this section we will consider the problem of finding a bent Hamilton cycle or path in two dimensions. Again, we first consider grids and then toroidal grids. The following lemma shows that if the graph Q(n, m) has both n, m > 2, then there is no bent Hamilton cycle or path. In such cases, it determines the minimal number of disjoint bent paths necessary to cover such a grid.

Lemma 3 The minimum size of a bent path covering of Q(n, m) is

• (n + m)/2 if n and m are both odd.

• n/2 if n is even and m is odd.

• min(n/2, m/2) if n and m are both even.

2^{+} 1^{+} 1^{+} 2^{−} 1^{−} 2^{−} 1^{+} 4^{+} 2^{+} 3^{+} 4^{−} 3^{−} 4^{−} 3^{+} 4^{+} 3^{+}

Figure 12: A Hamilton path in Q(3 · 3, 3 · 3) representing a bent Hamilton path in Q(3, 3, 3, 3).

Proof: Consider the edges in a path covering of Q(n, m) with the first dimension fixed. For a fixed x, there can be at most ⌊m/2⌋ edges of the form {(x, y), (x, y + 1)}; otherwise, some dimension would get used twice in a row. Similarly, for a fixed y, there are at most ⌊n/2⌋ edges of the form {(x, y), (x + 1, y)}. Thus the total number of edges is at most

⌊m/2⌋n + ⌊n/2⌋m.

Now taking the union of both types of edges together with any remaining isolated vertices gives a spanning subgraph with at least

C = nm − ⌊m/2⌋n − ⌊n/2⌋m

components.

If n and m are both odd, then C = (n + m)/2. If n is even and m is odd, then C = n/2. Unfortunately, if n and m are both even then C = 0, which is not informative and we must use a more refined argument.

Consider some bent path cover in Q(n, m) where n and m are both even. Let α_{i} be the number of edges used in row i, for i = 0, 1, 2, …, m − 1, and let β_{i} be the number of edges used in column j, for j = 0, 1, 2, …, n−1. As noted above, α_{i} ≤ n/2 and β_{j} ≤ m/2. Furthermore, it cannot be the case that there are even indices p < m and q < n such that

α_{p} = α_{p+1} = n/2 and β_{q} = β_{q+1} = m/2,

because that would force a 4-cycle. Now, a lower bound on the size of a minimum bent path cover can be obtained by maximizing the sum ∑ α_{i}+∑ β_{j} subject to the constraints mentioned above. Without loss of generality, let n ≥ m. It is not hard to see that this sum is (uniquely) maximized when β_{j} = m/2 for j = 0, 1, 2, …, n−1 and α_{i} +α_{i+1} = n−1 for i = 0, 2, …, n−2. Thus the maximum value of the sum is nm/2+(n−1)m/2 = nm−m/2, which implies that the path cover has at least m/2 components.

3^{+} 3^{+} 4^{−} 4^{+}  * * 3^{−} 4^{+} 3^{+} 4^{−}  1^{−} 2^{−} 2^{+} * *  * * * * 1^{+} 2^{+} *

Figure 13: A Hamilton path in Q(3 · 3, 3 · odd), representing a bent Hamilton path in Q(3, 3, 3, odd).

The examples given in Figure 15 show that the bounds on the minimum bent cover size can be achieved. Note that there are many other minimum bent covers, for example, constructed by using staircase shaped paths. □

We now focus on two dimensional toroidal grids. The proof of the previous lemma can be used to show that no bent Hamilton cycle exists if either n or m is odd. In fact, it yields the same lower bound for the number of bent Hamilton paths required to cover such graphs.

Corollary 2 The minimum size of a bent path covering of Q(n, m) is

• (n + m)/2 if n and m are both odd.

• n/2 if n is even and m is odd.

But what happens when both n and m are even? Does a bent Hamilton cycle exist in Q′(n, m)? In fact, yes it is possible. A construction is given in Figure 16.

Theorem 6 If n and m are even, then there exists a bent Hamilton cycle in Q′(n, m).

6 Summary - future work

We have proved that there exists a bent Hamilton cycle in the graph Q(n_{1}, n_{2}, …, n_{d}) as long as some n_{i} is even and d ≥ 3. When all n_{i} are odd we have proved that there is no bent Hamilton cycle; however, there is in the toroidal graph Q′. An interesting

3^{+} 4^{+} 3^{−} 4^{+} 3^{+} 3^{+} 3^{+} 4^{−} 3^{+} 4^{−} 3^{−} 4^{+} 3^{−} 4^{−}  1^{−} 2^{−} 2^{+} 1^{−} 2^{−} 2^{−} 1^{+} 1^{+} 1^{+} 1^{+} 2^{+} 1^{−} 2^{+} 1^{+}

Figure 14: A Hamilton path in Q(3 · 5, 3 · 5) representing a bent Hamilton path in Q(3, 3, 5, 5).

Figure 15: Minimum bent path covers: (a) n and m both odd, (b) n even, m odd, (c) n and m both even.

Figure 16: A bent Hamilton cycle in Q′(n, m) for n = 16 and m = 10.

open question is whether there are bent Hamilton cycles in Q′ with interesting non-trivial symmetries, as there was in Q′(3, 3, 3).

There are many other questions that the snake puzzle inspires. For example, what is the computational complexity of determining whether a snake can be twisted into a fixed rectangle? Into a fixed box? A snake of n cubes can be specified by a binary string of length n − 2, where a 0 stands for a straight-through connection and a 1 stands for an elbow connection. Since the snake has two ends the total number of non-isomorphic snakes is 2^{n−3} + 2^{⌈(n−2)/2⌉}. Algorithms for generating such strings are given in [4].

We conclude by listing two open problems. Goddyn and Gvozdjak [2] define the minimum run length of a Hamilton cycle in Q_{d} to be the least number of edges between edges in the same dimension among all dimensions. In the notation of Section 1, the minimum run length is the smallest value k for which there is an i such that

f(v_{i}, v_{i+1}) = f(v_{i+k}, v_{i+k+1}).

In all of the bent cycles and paths that we have created here, the minimum run length is 2. In fact, a Hamilton cycle or path is bent precisely when it’s minimum run length is at least 2. Under what conditions do Hamilton cycles and paths exist in Q and Q′ with minimum run length 3? Clearly, the minimum run length must be at most d. Can it ever be equal to d? Note that each of the nine cycles in Q′(3, 3, 3) have minimum run length 2.

References

[1] B. Bultena and F. Ruskey, Transition Restricted Gray Codes, Electronic Journal of Combinatorics, 3 (1996), paper R11, 11pp.

[2] L. Goddyn, L. and P. Gvozdjak, Binary Gray Codes with Long Bit Runs, Electronic Journal of Combinatorics, to appear.

[3] A. Itai, C.H. Papadimitriou, and J. Szwarcfiter, Hamilton Paths in Grid Graphs, SIAM Journal on Computing, 11 (1982) 676–686.

[4] A. Proskurowski, F. Ruskey, and M. Smith, Analysis of Algorithms for Listing Equivalence Classes of k-ary Strings Induced by Simple Group Actions, SIAM Journal on Discrete Mathematics, 11 (1998) 94-109.

[5] C.D. Savage, A survey of combinatorial Gray codes, SIAM Review 39 (1997) 605–629.

[6] W.T. Trotter and P. Erdös, When the Cartesian product of directed cycles is Hamiltonian, Journal of Graph Theory, 2 (1978) 137-142.