On the Hamiltonicity of Directed σ − τ Cayley Graphs (Or: A Tale of Backtracking)

Frank Ruskey ^{∗}  Ming Jiang

Andrew Weston ^{†}

Department of Computer Science

University of Victoria, Victoria, B.C., V8W 3P6, Canada

January 2, 2001

Abstract

Let τ be the 2-cycle (1 2) and σ the n-cycle (1 2 ⋯ n). These two cycles generate the symmetric group S_{n}. Let G_{n} denote the directed Cayley graph Cay({τ, σ} : S_{n}). Based on erroneous computer calculations, Nijenhuis and Wilf ([NiWi75], pg. 238 and [NiWi78], pg. 288) give as an exercise to show that G_{5} does not have a Hamilton path. To the contrary, we show that G_{5} is Hamiltonian. Furthermore, we show that G_{6} has a Hamilton path. Our results illustrate how a little theory and some good luck can save a lot of time in backtracking searches.

Keywords: Directed Cayley graph, Hamiltonian cycle, backtracking. AMS Classification: 05C45, 68-04.

∗Research supported in part by the Natural Sciences and Engineering Research Council of Canada under Operating Grant A3379.

†Research supported in part by an NSERC undergraduate scholarship.

1 Introduction

There has been much research interest in Hamiltonicity properties of Cayley Graphs. This interest is fueled by the very attractive conjecture (of Parsons and others) that all connected undirected Cayley graphs are Hamiltonian, and most research has centered on undirected Cayley graphs. In the case of directed Cayley graphs, the question is messier, in part because of the existence of examples of directed Cayley graphs that are not Hamiltonian and there are even examples that don’t have Hamilton paths. Among directed Cayley graphs without Hamilton paths, the “sigma-tau” graph for n = 5 is often cited (e.g., Nijenhuis and Wilf [NiWi75], [NiWi78], Holsztyński and Strube [HoSt], Wilf [Wilf], Witte [Witt], and Witte and Gallian [WiGa]).

To be precise, let

τ = (1 2) and σ = (1 2 ⋯ n),

and let G_{n} denote the Cayley graph Cay({σ, τ} : S_{n}). We will show that the sigma-tau examples should not be used because G_{4} has a Hamilton path but is not Hamiltonian, G_{5} is Hamiltonian, and G_{6} has a Hamilton path. Whether G_{6} has a Hamilton cycle is not known.

In a recent tour-de-force Compton and Williamson [CoWi] have shown that the undirected Cayley graph Cay({τ, σ, σ^{−1}} : S_{n}) is Hamiltonian for all n. The question of determing the Hamiltonicity of G_{n} appears to be much more difficult.

Our basic technique in discovering these Hamilton paths and cycles is the timehonored technique of backtracking. The paper is organized into five sections. In this first section we introduce the problem and notation and present a few simple lemmas. The next three sections present our results for n = 4, 5, 6. The final section discusses the backtracking techniques that were used.

We regard Cayley graphs as having edges labeled by a generator and Hamilton paths and cycles as consisting of a string of edge labels. Thus, a Hamilton path in G_{n} is a string of length n! − 1 over the alphabet {σ, τ}.

The next two lemmas help us to prune the backtracking tree.

Lemma 1 For n > 2, if G_{n} has a Hamiltonian path then that path must contain a sub-path labeled στσσ.

Proof. This follows immediately from the identity (τσ)^{n−1} = id. □

Lemma 2 Any Hamiltonian cycle in G_{n} does not contain the subpath τσ^{n−2}τ.

Proof. Assume that there is a Hamilton cycle C that starts with τσ^{n−2}τ. Then there is no way to exit the vertex x = τσ^{n−1}. It cannot be entered from τσ^{n−2}, nor can it be exited to τσ^{n} = τ. Thus x must both be exited and entered from xτ, which is impossible. □

Although G_{n} is directed, it shares one nice property with undirected Cayley graphs, which is not true in general for directed Cayley graphs. If A is a string, then by A^{R} we denote the reversal of A.

Lemma 3 If A is a Hamilton path (cycle) in G_{n}, then A^{R} is also a Hamilton path (cycle) in G_{n}.

Proof. Consider the Cayley graph G_{n}^{−1} = Cay({τ, σ^{−1}} : S_{n}). Clearly, if A is a path in G_{n}, then A^{R}, with σ replaced by σ^{−1}, is a path in G_{n}^{−1}. We will show that G_{n} and G_{n}^{−1} are isomorphic, by an isomorphism that maps τ edges to τ edges and σ edges to σ^{−1} edges; from this the lemma follows immediately. Consider the permutation

g = (1 2)(3 n)(4 n−1) ⋯ (⌊(n+3)/2⌋ ⌈(n+3)/2⌉).

Define the mapping x → xg, where x ∈ S_{n}. We will show that if (x, xh) is an edge of G_{n}, then (xg, xhg) is an edge of G_{n}^{−1}. Either h = τ, or h = σ. If h = τ, then

τg = gτ = (1)(2)(3 n)(4 n−1) ⋯

and (xg, xgτ) ∈ E(G_{n}^{−1}). If h = σ then

σg = gσ^{−1} = (1 3)(2)(4 n)(5 n−1) ⋯

and (xg, xgσ^{−1}) ∈ E(G_{n}^{−1}). □

Thus when we speak of “non-isomorphic” Hamilton paths we consider two paths to be isomorphic if one is the reversal of the other. Similarly, two Hamilton cycles are isomorphic if one can be obtained from the other by rotation or reversal.

Lemma 4 Any Hamilton path in G_{n} that starts at the permutation 12 ⋯ n and ends at x_{1}x_{2} ⋯ x_{n} must satisfy x_{1} = 2.

Proof. This is proven for a spanning supergraph of G_{n} in [JiRu]. □

However, unlike the Faber-Moore graphs of [JiRu], not all permutations of 1, 3, …, n seem to be possible ending permutations of Hamilton paths starting at 12 ⋯ n.

It might be remarked that the approach of Compton and Williamson [CoWi] will not work in the directed case. Their cycle successively lists the elements of the cosets of ⟨σ⟩, a coset at a time. That approach fails work in the directed case since (τσ^{n−1})^{n−1} = (τσ^{−1})^{n−1} = id.

In what follows we use the integer k to denote τσ^{k−1}. To avoid confusion, these integers will be enclosed in square brackets; e.g., τσστσ = [32].

2 The case n = 4

To understand the proof of the following lemma the reader should refer to Figure 1, which shows Cay({τ, σ} : S_{4}). It is interesting that the graph Cay({τ, σ, σ^{−1}} : S_{4}) is isomorphic to Cay({(12), (23), (34)} : S_{4}), the “permutohedron” of S_{4} (e.g., Figure 1 of [RuSa]). Directed edges in Figure 1 correspond to σ and the undirected (triple lined) edges correspond to τ.

Lemma 5 The graph G_{4} is not Hamiltonian.

Proof. Assume to the contrary that G_{4} has a Hamilton cycle C. We will derive a contradiction. By Lemma 2, C does not contain [3]τ; i.e., the path is a sequence of 2’s and 4’s. Our proof makes use of the identities [2]^{3} = [4]^{3} = [24]^{3} = id (valid only for n = 4). By [2]^{3} = id, the cycle C must not contain the subpath [224]. By [4]^{3} = id, the cycle C must not contain the subpath [444]. By [24]^{3} = id it must contain the subpath [44]. Hence, C must contain the subpath [424424] = id, which is a contradiction since this subpath contains only 20 vertices. □

Lemma 6 There are exactly 3 non-isomorphic Hamilton paths in G_{4}, which are listed below.

τσσστστσσστσσστστσστσσσ = [4244234] (1)

τσσστσσστσστστσσστσσστσ = [4432442] (2)

στστσσστσσστστσσστστσσσ = σ[2442424] (3)

It is interesting to note that if (1) and (2) are considered as circular arrangements of symbols, then one may be obtained from the other by traversing the strings in opposite directions.

3 The case n = 5

For n = 5 there exist Hamilton cycles and Hamilton paths that are not cycles in G_{n}. Recall that two cycles are considered isomorphic if one may be obtained from the other by rotation or reversal. We list the lexicographically smallest cycle or path from each equivalence class.

Lemma 7 There are exactly 5 non-isomorphic Hamilton cycles in G_{5}, which are listed below. Each cycle contains 36 τ’s and 84 σ’s (or, more generally, 12 each of 2’s, 3’s, and 5’s).

A_{1} = [223252522355233533553355522332252335] (4)

[figure: 1432; 2143; 3214; 4321; 1342; 3142; 3421; 2314; 4231; 2143; 4213; 1423; 4132; 1243; 1324; 3124; 2431; 4312; 4123; 3412; 2413; 3241; 2341; 1234]

Figure 1: The graph Cay({τ, σ} : S_{4}).

A_{2} = [223323522522355235335535225323325553] (5)

A_{3} = [223323522535525335|223323522535525335] (6)

A_{4} = [22332553252|252355233223552353|3532553] (7)

A_{5} = [223533555233235225|223533555233235225] (8)

Note that A_{3} and A_{5} may be written in the form AA. The most beautiful of the cycles is A_{4}. It has the property that it may be written in the form A\overline{A}^{R}\overline{A}A^{R} where \overline{A} is A but with 2’s and 3’s interchanged. For example, take A = 252355233. Now consider the cosets of ⟨σ⟩; to each coset there is an associated either a [5], or a [2] and a [3]. The [2],[3] cosets of A and \overline{A} are matched as shown below.

A = 2 5 2 3 5 5 2 3 3
a  b c  d e a
\overline{A} = 3 5 3 2 5 5 3 2 2
f  b e  d c f

The cosets of \overline{A}^{R} and A^{R} are matched in a similar manner (but reversed). It is our hope that A_{4} may be used as the basis of an inductive proof that G_{n} is Hamiltonian for all n ≥ 5.

There also exist Hamilton paths in G_{5} which are not Hamilton cycles.

Lemma 8 There are 430 non-isomorphic Hamilton paths in G_{5} that are not Hamilton cycles. Of these, 6 are symmetric in the sense that such a path A satisfies A = A^{R}.

Here is a symmetric Hamiltonian path in G_{5}. All 6 symmetric paths had 41 τ’s and 78 σ’s.

[33532233252252332234]τ[33532233252252332234] ^{R}

4 The case n = 6

Through our programs we have found that G_{6} can be partitioned into two disjoint cycles, one of length 714 and the other of length 6. This cycle was somewhat difficult to find. We experimented with various ratios of τ calls before σ calls and found the 714-cycle by using a 3/7 ratio (recall the 36 to 84 split of Lemma 7).

Lemma 9 The graph G_{6} has a Hamilton path.

Proof. In Figure 2 is listed a cycle of length 714 in G_{6}. The six missing vertices, shown below, also form a cycle in G_{6}.

153246, 246153, 324615, 461532, 532461, 615324

A path may be formed, for example, by taking the six permutations above followed by 165324 in the 714-cycle. □

5 The Backtracking Algorithms

In this section we describe our backtracking implementations. Our overriding concerns were to keep the implementation efficient and as simple as possible.

First a global adjacency list structure was created to represent the graph. With each vertex v four values are stored. Three values, vτ, vσ, and vσ^{−1}, are static. The fourth, visited(v), is dynamic and keeps track of whether v is on the path constructed so far, or not.

To obtain the results of the n = 5 section we first used the naive backtracking algorithm of Figure 3 which took 99,000 seconds on a Sun MP 690, when carefully implemented in C. We used gen(στσσ) as the initial call, which is justified by Lemma 1. We then went through two successive refinements in order to speed-up the algorithm.

Our first refinement of the algorithm took advantage of Lemma 2 and had the form shown in Figure 4. The variable sc is the number of consecutive σ’s at the end of A. The initial call is gen(στσσ, 2). This simple change had a dramatic effect; it reduced the running time to 850 seconds, but we still felt this was to slow to attack the n = 6 problem.

Our second refinement reduced the running time to only 11 seconds. Consider a vertex v of G_{n} as the backtracking is proceeding. We say that v is touched if it is not properly on the cycle constructed so far (e.g., is not a prefix of A), but one of it’s neighbors is on the cycle. Observe that if a vertex is touched twice by A, then A cannot be extended to a Hamilton cycle. There are three possible ways that a vertex may be touched, as shown in Figure 5. By using this observation we are led to our second refinement as outlined in Figure 6.

For n = 6 we were only able to explore a minute fraction of the backtracking tree. Thus we were unable to determine whether G_{6} is Hamiltonian.

6 Acknowledgement

We thank Herb Wilf for his encouragement and his suggestion to look at G_{6}, which is what got us started on this research.

213456  123456  612345  162345  516234  451623  345162  234516  623451  263451
126345  512634  451263  345126  634512  364512  236451  326451  132645  513264
451326  645132  264513  624513  362451  136245  513624  451362  245136  425136
642513  462513  346251  134625  513462  251346  625134  265134  426513  342651
134265  513426  651342  561342  256134  526134  452613  345261  134526  613452
261345  621345  562134  456213  345621  435621  143562  413562  241356  421356
642135  564213  356421  135642  213564  123564  412356  641235  564123  356412
235641  325641  132564  312564  431256  643125  564312  256431  125643  215643
321564  432156  643215  564321  156432  516432  251643  521643  352164  435216
643521  164352  216435  126435  512643  351264  435126  643512  264351  624351
162435  612435  561243  356124  435612  243561  124356  214356  621435  562143
356214  536214  453621  543621  154362  514362  251436  625143  362514  436251
143625  413625  541362  254136  625413  362541  136254  316254  431625  341625
534162  253416  625341  162534  416253  146253  314625  531462  253146  625314
462531  642531  164253  614253  361425  536142  253614  425361  142536  412536
641253  364125  536412  253641  125364  215364  421536  241536  624153  362415
536241  153624  415362  145362  214536  621453  362145  632145  563214  653214
465321  645321  164532  216453  321645  532164  453216  543216  654321  165432
216543  321654  432165  342165  534216  354216  635421  163542  216354  421635
542163  452163  345216  634521  163452  216345  521634  251634  425163  245163
324516  632451  163245  516324  451632  541632  254163  325416  632541  163254
416325  146325  514632  154632  215463  321546  632154  463215  546321  456321
145632  214563  321456  231456  623145  263145  526314  256314  425631  142563
314256  631425  563142  653142  265314  426531  142653  314265  531426  351426
635142  365142  236514  423651  142365  412365  541236  654123  365412  635412
263541  126354  412635  541263  354126  534126  653412  265341  126534  412653
341265  431265  543126  654312  265431  126543  312654  132654  413265  541326
654132  265413  326541  236541  123654  213654  421365  542136  654213  365421
136542  316542  231654  423165  542316  654231  165423  615423  361542  631542
263154  426315  542631  452631  145263  314526  631452  361452  236145  523614
452361  145236  614523  164523  316452  231645  523164  452316  645231  465231
146523  416523  341652  234165  523416  652341  165234  615234  461523  346152
234615  523461  152346  512346  651234  561234  456123  345612  234561  324561
132456  613245  561324  456132  245613  425613  342561  134256  613425  163425
516342  156342  215634  125634  412563  341256  634125  563412  256341  526341
152634  415263  341526  431526  643152  264315  526431  152643  315264  135264
413526  641352  264135  624135  562413  356241  135624  315624  431562  341562
234156  324156  632415  563241  156324  415632  241563  421563  342156  634215
563421  653421  165342  216534  421653  241653  324165  532416  653241  165324
416532  146532  214653  321465  532146  352146  635214  463521  146352  416352
241635  524163  352416  635241  163524  613524  461352  246135  524613  352461
135246  315246  631524  463152  246315  524631  152463  512463  351246  531246
653124  563124  456312  245631  124563  312456  631245  361245  536124  453612
245361  124536  612453  162453  316245  531624  453162  543162  254316  625431
162543  612543  361254  631254  463125  546312  254631  125463  312546  132546
613254  461325  546132  254613  325461  235461  123546  213546  621354  462135
546213  354621  135462  315462  231546  623154  462315  642315  564231  156423
315642  231564  423156  243156  624315  562431  156243  516243  351624  435162
243516  423516  642351  462351  146235  416235  541623  354162  235416  623541
162354  612354  461235  546123  354612  534612  253461  125346  612534  461253
346125  436125  543612  254361  125436  215436  621543  362154  436215  346215
534621  153462  215346  621534  462153  642153  364215  536421  153642  513642
251364  521364  452136  645213  364521  136452  213645  123645  512364  451236
645123  465123  346512  436512  243651  124365  214365  521436  652143  365214
436521  143652  413652  241365  524136  652413  365241  136524  316524  431652
243165  524316  652431  165243  615243  361524  436152  243615  524361  152436
512436  651243  365124  635124  463512  246351  124635  214635  521463  251463
325146  632514  463251  643251  164325  614325  561432  651432  265143  326514
432651  143265  514326  154326  615432  261543  326154  236154  423615  542361
154236  514236  651423  561423  356142  235614  423561  142356  614235  164235
516423  351642  235164  325164  432516  342516  634251  364251  136425  316425
531642  253164  425316  245316  624531  264531  126453  312645  531264  453126
645312  465312  246531  124653  312465  132465  513246  651324  465132  246513
324651  234651  123465  213465  521346  652134  465213  346521  134652  314652
231465  523146  652314  562314  456231  546231  154623  514623  351462  235146
623514  263514  426351  142635  514263  154263  315426  135426  613542  261354
426135  542613  354261  534261  153426  615342  261534  426153  342615  432615
543261  453261  145326  614532  261453  326145  532614  352614  435261  143526
614352  261435  526143  256143  325614  432561  143256  413256  641325  564132
256413  526413  352641  532641  153264  415326  641532  264153  326415  236415
523641  152364  415236  641523  364152  634152  263415  623415  562341  156234
415623  145623  314562  134562

Figure 2: A cycle of length 714 in G_{6}. procedure gen ( A ) begin

if A is a Hamilton cycle then PrintIt else if A is not a cycle then begin gen( Aτ ); gen( Aσ );

end; end {of gen};

Figure 3: Naive Backtracking Algorithm.

procedure gen ( A, sc ) begin

if A is a Hamilton cycle then PrintIt else if A is not a cycle then begin

if sc ≠ n − 2 then gen( Aτ, 0 );

gen( Aσ, sc + 1 );

end; end {of gen};

Figure 4: First refinement.

[figure: v; v; v]

Figure 5: The three ways vertex v can be touched. procedure gen ( A, g ) begin

if A is a Hamilton cycle then PrintIt else if A is not a cycle then begin

if touched(Aσ) = false then begin touched(Aσ) := true; gen( Aτ, τ ); touched(Aσ) := false;

end; if g = τ then begin

if touched(Aσ^{−1}) = false then begin touched(Aσ^{−1}) := true;

gen( Aτ, σ );
touched(Aσ^{−1}) := false;

end; end else begin

if touched(Aτ) = false then begin touched(Aτ) := true;

gen( Aτ, σ );
touched(Aτ) := false;

end; end;

end; end {of gen};

Figure 6: Second refinement.

References

[CoWi] R.C. Compton and S.G. Williamson, “Doubly Adjacent Gray Codes for the Symmetric Group”, TR-CS91-220, U.C. San Diego, 1991.

[HoSt] W. Holsztyński and R.F.E. Strube, “Paths and Circuits in Finite Groups”, Discrete Mathematics, 22 (1978) 263-272.

[JiRu] M. Jiang and F. Ruskey, “Determining the Hamilton-Connectedness of Certain Vertex-Transitive Graphs”, Discrete Mathematics, to appear.

[RuSa] F. Ruskey and C. Savage, “Hamilton Cycles which Extend Transposition Matchings in Cayley Graphs of S_{n}”, SIAM J. Discrete Mathematics, to appear.

[NiWi75] A. Nijenhuis and H.S. Wilf, Combinatorial Algorithms, 1st ed., Academic Press, 1975.

[NiWi78] A. Nijenhuis and H.S. Wilf, Combinatorial Algorithms, 2nd ed., Academic Press, 1978.

[Wilf] H.S. Wilf, Combinatorial Algorithms: An Update, SIAM, CBMS 55, 1989.

[Witt] D.S. Witte, “On Hamiltonian Circuits in Cayley Diagrams”, Discrete Mathematics, 38 (1982) 99-108.

[WiGa] D. Witte and A. Gallian, “A Survey: Hamiltonian Cycles in Cayley Graphs” Discrete Mathematics, 51 (1984) 293-304.

John Milnor’s example (as presented in [WiGa]). Let n divide r^{2} −r+1 and define the group

G = ⟨a, b | a^{2} = b^{3} = c^{n} = id, cb = bc^{r−1}⟩,

where c = a^{−1}b^{−1}ab.

John Milnor’s example (as presented in [HoSt]). Let n divide r^{2} − r + 1 and define the group

G = ⟨a, b | a^{2} = b^{3} = (ab)^{6} = (abab^{2})^{n} = id⟩.

If n = 2 then one obtains the following digraph (isomorphic to C_{2} × A_{4}).