/^creative ^commor
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 8 (2015) 35-53
ARS MATHEMATICA CONTEMPORANEA
Hamilton paths in Cayley graphs on Coxeter groups: I*
Brian Alspach
School of Mathematical and Physical Sciences, University of Newcastle Callaghan, NSW 2308, Australia
Received 11 July 2013, accepted 7 January 2014, published online 18 April 2014
Abstract
We consider several families of Cayley graphs on the finite Coxeter groups An, Bn, and Dn with regard to the problem of whether they are Hamilton-laceable or Hamilton-connected. It is known that every connected bipartite Cayley graph on An, n > 2, whose connection set contains only transpositions and has valency at least three is Hamilton-laceable. We obtain analogous results for connected bipartite Cayley graphs on Bn, and for connected Cayley graphs on Dn. Non-bipartite examples arise for the latter family.
Keywords: Hamilton path, Cayley graph, Coxeter group, Hamilton-connected, Hamilton-laceable. Math. Subj. Class.: 05C25, 05C70
1 Introduction
The motivational stream for this paper is a confluence of many rivulets varying in age and intrigue. We now explore this history and do so in spite of postponing definitions until completing the brief excursion.
The oldest is Lovasz's 1969 question [15] asking whether every connected vertex-transitive graph has a Hamilton path. A closely related thread arose more or less simultaneously, namely, the question of whether every connected Cayley graph has a Hamilton cycle. The latter question has attracted considerable attention for more than forty years. There have been three survey papers of which I am aware [2, 9, 17] and many, many individual papers dealing with the question. References [10, 11, 14] are examples of some recent papers on the topic.
Altshuler [6] studied Hamilton cycles in certain embeddings of trivalent graphs on the torus where all faces are hexagons. He was unable to completely settle the problem of
* Dedicated to Dragan Marusic on the occasion of his sixtieth birthday.
E-mail address: brian.alspach@newcastle.edu.au (Brian Alspach)
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
36
Ars Math. Contemp. 8 (2015) 149-162
whether all such graphs are hamiltonian. Many of these graphs (but not all) are Cayley graphs on dihedral groups. This was the first specific instance of looking for Hamilton cycles in Cayley graphs on dihedral groups.
The author and Zhang [5] proved that all connected trivalent Cayley graphs on dihedral groups are hamiltonian. Unfortunately, we were unable to extend the result to any larger valency. So the general problem of determining whether all connected Cayley graphs on dihedral groups are hamiltonian remains unresolved. There has been some progress. It has been known for almost thirty years that the problem has an affirmative answer if it could be proved that the answer is yes when all the elements in the connection set are reflections. As a corollary of a general result in a recent paper [4], we now know that all connected Cayley graphs on dihedral groups are hamiltonian whenever the order of the group is a multiple of 4.
Two apparently unrelated threads come from computer science. The older of the two is related to algorithms for generating all the permutations of an n-set [13, 16]. Several of the algorithms correspond to a Hamilton path in a Cayley graph on the symmetric group Sn with a connection set composed of transpositions. Recently, there has been considerable interest in other Cayley graphs on symmetric groups, where the connection set contains only transpositions. The most celebrated graph of this type is the star graph of dimension n [1] (as it frequently is called).
The penultimate thread is fairly new and arises in computational biology. Analysis of genomes evolving by inversions leads to a graph theoretic interpretation that involves signed permutations [12]. This involves the Cayley graphs we study in Sections 3 and 4.
An older paper [8] actually ties these threads together (although it may not yet be apparent). In that paper the following theorem appears.
Theorem 1.1. Let G be a finite group generated by reflections R1,..., Rn. Then there is a hamiltonian circuit in the Cayley diagram for G corresponding to these generators.
Upon reading Theorem 1.1, we might think this settles the problem for connected Cayley graphs on dihedral groups because, as mentioned above, it suffices to settle that problem when all the members of the connection set are reflections. However, a careful reading of [8] leads to the discovery that they prove there is a presentation for every finite Coxeter group so that the corresponding Cayley graph has a Hamilton cycle. It is highly likely that Theorem 1.1 is true, but it is yet to be proven.
The final thread arises out of a strong generalization of Theorem 1.1 for symmetric groups (see Theorem 2.3 in the next section). The purpose of this paper is to start extending Theorem 2.3 to Cayley graphs on other Coxeter groups. The two main results are Theorems 4.3 and 5.2.
We are ready to start useful background information. The Cayley graph Cay(G; S) on the group G with connection set S is the graph whose vertex set is the set of elements of G, with an edge joining g and h if and only if h = gs for some s G S. There is a restriction on the connection set S, namely, 1 G S and S is inverse-closed, that is, s G S if and only
if s-1 G S.
We shall use two notations for permutations because each of them is convenient for certain contexts. One common notation is cyclic notation in which a permutation is written as a product of disjoint cycles. The cycles are enclosed in parentheses and upon observing a cycle ( • • • i j • • •), this is to be interpreted as meaning the permutation maps i to j. There are no commas in this notation, instead, the elements in the cycles are separated by extra
B. Alspach: Hamilton paths in Cayley graphs on Coxeter groups: I
37
space. We also adopt the convention that fixed points, that is, 1-cycles, are not written down. Thus, the transposition interchanging i and j is written (i j).
The other notation for permutations we use is range notation. That is, if we write a permutation as a1a2... an, we mean the permutation that maps i to aj for i = 1, 2,... ,n. Thus, the identity permutation in the symmetric group S5 is written as 12345. We shall employ the Orbit-Stabilizer Theorem and state it now for convenience.
Theorem 1.2. If G is a permutation group acting on a finite set A, then the order of G is given by
|G| = |O(x)||Gx|,
where x e A, O(x) denotes the orbit of G containing x, and Gx is the stabilizer of x.
A graph X is Hamilton-connected whenever one can find a Hamilton path joining any two arbitrarily chosen vertices. Similarly, a bipartite graph X, for which both parts have the same cardinality, is Hamilton-laceable whenever one can find a Hamilton path joining any two arbitrarily chosen vertices lying in different parts.
2 The symmetric groups
A Coxeter group is a group generated by reflections R1, R2,..., Rn such that the only other relations are of the form (RjRj)k = 1. Given a Coxeter group G, we associate a graph with it, called a Coxeter diagram, where there is a vertex associated with each of the generating reflections.
It is easy to see that R and Rj commute if and only if (RjRj)2 = 1. So we do not place an edge in the Coxeter diagram if and only if (RjRj )2 = 1. If (RjRj )3 = 1, then we join Rj and Rj by an edge and do not label the edge. Finally, if (RjRj)k = 1 and k > 3, then we join Rj and Rj by an edge and label the edge with k.
The symmetric group Sn is a Coxeter group corresponding to the Coxeter diagram given in Figure 1 with the last edge removed. (Thus, we see that Sn is the Coxeter group An-1.) The generator Rj, 1 < i < n — 1, is the reflection of En, n-dimensional euclidean space, through the orthogonal complement of the vector with -1 in coordinate i, 1 in coordinate i + 1 and zeros in all other coordinates. We present the known results for the symmetric groups for completeness and because it takes little space.
Definition 2.1. Let S be a collection of transpositions in Sn. We define an auxiliary graph aux(S) by letting the vertices be labelled 1, 2,... ,n and joining i and j with an edge if and only if (i j) e S.
The following proposition is easily proved by induction using Theorem 1.2.
Proposition 2.2. If X = Cay(Sn; S), where S consists of transpositions only, then X is connected if and only if aux(S) is connected.
The proof given in [8] for Theorem 1.1 applies to the connection set consisting of the transpositions (1 2), (2 3),..., (n — 1 n). The next theorem is a strong generalization in that it tells us that all of the connected Cayley graphs on the symmetric group, whose connection sets contain only transpositions, are Hamilton-laceable. This vastly extends the connection sets involved, and strongly extends the conclusion as well. Of course, Hamilton-laceable is the best we can hope for because the graphs are bipartite.
Theorem 2.3. (Araki [7]) If X = Cay(Sn; S) is connected, S consists of transpositions only, and n > 4, then X is bipartite and Hamilton-laceable.
38
Ars Math. Contemp. 8 (2015) 149-162
3 Path extension and Johnson graphs
The proofs of the main results to follow are variations on a single theme. Namely, choose a single vertex u and a target vertex v with the object of finding a Hamilton path joining u to v. We proceed by building longer and longer paths from u until we have a path from u that spans all the vertices and terminates at v. We call this technique path extension.
The following lemma is the path extension lemma and is used many times. We employ the notion of a quotient graph arising from a partition of the vertex set. It is defined as follows. Given a graph X and a partition Ai, A2,..., At of its vertex set, we define the quotient graph with respect to the partition to be the graph of order t whose vertices correspond to the parts, where two vertices are adjacent if and only if there was at least one edge in X between the corresponding parts.
We remind the reader that a k-matching is a set of k vertex-disjoint edges.
Lemma 3.1. Let X be a graph whose vertex set is partitioned into parts Ai,A2,..., At, let Yi denote the subgraph induced on Ai, i = 1,2,... ,t, and let X/A denote the quotient graph with respect to the partition. We are interested in two scenarios.
(i)	If each Yi is Hamilton-connected, then we assume that whenever two parts are joined by an edge, there is in fact a 3-matching between the parts. In this case, if there is a Hamilton path in X/A from Ai to Aj, then there is a Hamilton path in X joining any vertex in Ai to any vertex in Aj.
(ii)	If each Yi is Hamilton-laceable, let Bi, Ci denote the parts of the bipartition of Yi. We now assume that whenever two parts Ai and Aj are joined by an edge, then there is a 2-matching between Ai and Aj so that the four end vertices of the two edges intersect each of the sets Bi, Bj ,Ci, Cj. In this case, if there is a Hamilton path in X/A from Ai to Aj, then there is a Hamilton path joining any vertex of Ci to any vertex of one of Bj or Cj, and any vertex of Bi to any vertex of the other one of Bj or Cj.
Proof. In scenario (i), choose an arbitrary vertex u in Ai. Let v be the target vertex in Aj. There is a Hamilton path P' joining Ai and Aj in X/A. Let Ak be the second vertex of P'.
There must be a vertex u' e Ai distinct from u such that u' has a neighbor w e Ak because there is a 3-matching between Ai and Ak. Thus, take a path from u to u' that spans the vertices of Ai. Then add on the edge from u' to w.
There now must be a vertex w' e Ak, distinct from w, with a neighbor in the next part. We then extend the path by adding on a path from w to w' that spans the vertices of Ak.
We continue in the obvious way noting that we may enter Aj, the last part in P', at a vertex distinct from v because there is a 3-matching between Aj and the preceding part on P'. We then complete the path to a Hamilton path from u to v by adding a path spanning Aj that terminates at v.
The proof when each Yi is bipartite is essentially the same outside of respecting the bipartition of the subgraphs.	□
Recall that the Johnson graph J(n, r) has all the r-subsets of an n-set as its vertices, where two vertices are adjacent if and only if their corresponding subsets have exactly r - 1 elements in common. We need to define another graph. Let C = [ai, a2,..., am} be a non-empty subset of [0,1,2,... ,n} such that the elements are listed in the order ai < a2 < • • • < am. We define the graph QJ(n, C) in the following way. For each
B. Alspach: Hamilton paths in Cayley graphs on Coxeter groups: I
39
a,i € C, we include a copy of the Johnson graph J(n, aj). Thus far the Johnson graphs are vertex-disjoint with no edges between them. We then insert edges between J(n, a») and J(n, ai+1), for each i, using set inclusion, that is, we join an aj-subset Si and an ai+1-subset S2 if S1 is contained in S2.
The graph QJ(n, C) can be pictured as having levels made up of Johnson graphs with edges between successive levels based on set inclusion. The following theorem is proved in [3].
Theorem 3.2. The graph QJ (n, C) is Hamilton-connected for every non-empty C. 4 Wreath products
Because we shall be working with signed permutations throughout the rest of the paper, we adopt a convention that simplifies notation. Instead of writing —k for a positive integer k, we write k. We extend this in the obvious way in that k = k, and use x for — x.
Consider the Coxeter diagram shown in Figure 1. The generator Rj, 1 < i < n — 1, is the reflection of En through the orthogonal complement of the vector with 1 in coordinate i, 1 in coordinate i +1 and zeros in all other coordinates. The generator Rn is the reflection of En through the orthogonal complement of the vector with 1 in coordinate n and zeros in all other coordinates. This is the Coxeter group Bn and it is easy to see that
R1
R2
Rs
Rn
1
Rn
Figure 1
4
it is isomorphic to the wreath product Sn l S2. This group may be visualized as the set of all permutations acting on the set {1,1,2,2,..., n, n} such that if f (i) = y, then f (i) = y. This then gives us a compact notation for the elements of Sn I S2, namely, we write
a1a2 . . . an
to be the permutation mapping i to a» and i to aj for i = 1,2,... ,n. That is, the elements are all the signed permutations of 1,2,... ,n.
Note that Sn IS2 is imprimitive with the complete block system composed of the blocks {i, i} for i = 1,2,..., n. Thus, there is a natural homomorphism
f : Sn l S2 ^ Sn,
with kernel isomorphic to S2, representing the action on the block system. If ip(f) = (i j) is a transposition in Sn, then either f = (i j)(i j)g or f = (i j)(i j)g, where g is in the kernel. When g = 1, we call such an element of Sn l S2 a double transposition. If f € Sn l S2 is a transposition, it is easy to see that f € ker(y), that is, f = (i i) for some i in cyclic notation.
40
Ars Math. Contemp. 8 (2015) 149-162
Let X = Cay(Sn l S2; S), where S contains only transpositions and double transpositions. We define an auxiliary graph aux(S) in this case similar to what we did for Cayley graphs on Sn. The vertices are again the integers 1, 2,3,..., n. We join i and j by an edge if and only if there is a double transposition f e S for which the homomorphic image
¥>(f) = (ij).
The next result provides some useful structural information.
Lemma 4.1. If S is a collection of n — 1 double transpositions in Sn lS2 such that aux(S) is a tree, then the subgroup (S) generated by S is isomorphic to Sn, has two orbits such that i and i belong to different orbits for 1 < i < n, has index 2n in Sn lS2, and the graphs induced on the left cosets of (S) are precisely the components of Cay(Sn l S2; S).
Proof. We induct on n. When n = 2, S contains a single double transposition. We can check easily that the conclusions follow as there are only two possibilities for the double transposition. Let S be a collection of double transpositions satisfying the hypotheses for some n > 2, and assume the result holds for n — 1.
We may assume the elements on which Sn l S2 is acting are labelled so that n is a leaf of the tree aux(S). Remove from S the double transposition t involving the element n and let S' denote the set of n — 1 transpositions left over. The subgroup (S') fixes n and n, and by induction satisfies the conclusions of the theorem when restricted to {1,1,2,2,..., n — 1,n—T }.
Thus, (S)n, the stabilizer of n, has order (n — 1)! and is isomorphic to Sn-1. If t = (n y)(n y), then let the orbit of (S') containing y be O1. Because t maps n to y and the other n — 1 double transpositions map elements of O1 to elements of O1, the orbit of (S) containing n is {n} U O1. So the stabilizer of n has order (n — 1)! and the orbit containing n has cardinality n. We then know that |(S)| = n! by Theorem 1.2. Hence, (S) is isomorphic to Sn.
Clearly, the orbit containing n is {n} U O2, where O2 is the other orbit of the restriction of Sn-1 to {1,1,2, 2,..., n — 1, n — 1}. Hence, (S) has two orbits such that {i, i} intersects both orbits for 1 < i < n.
Because |Sn l S2| = 2nn! and |(S)| = n!, it certainly is the case that (S) has index 2n in the Sn l s2. So that property holds.
Examining the Cayley graph Cay(Sn l S2; S), we know that we have a component consisting of the vertices corresponding to the elements of (S). Because left-multiplication is an automorphism of a Cayley graph, the components of this Cayley graph are induced on the left cosets of (S).	□
Lemma 4.2. If X = Cay(Sn I S2; S), where S contains only transpositions and double transpositions, then X is connected if and only if S contains at least one transposition and aux(S) is connected.
Proof. If aux(S) is not connected, then it is clear that X is not connected. Thus, if X is connected, then aux(S) is connected.
Multiplying on the right by a double transposition either switches two positions, or switches two positions and negates both entries. Thus, if S contains only double transpositions, the signed permutation 123 ... n is not in the same component as a signed permutation with a single negative entry. Hence, if X is connected, then S must contain a transposition. This completes the proof of one direction.
B. Alspach: Hamilton paths in Cayley graphs on Coxeter groups: I
41
We now assume that aux(S) is connected and S contains a transposition (i i). Let T be a spanning tree of aux(S). Let Y = Cay(Sn I S2; T). We know from Lemma 4.1 that Y has 2n components so let Y' be the component containing 123 ... n.
Let I (A) denote the involution consisting of the product of the transpositions (k k) as k runs through elements of A, where A is a subset of {1,2,..., n}. Left multiplication by I (A) is an automorphism of Y mapping Y' to the component containing I (A).
Consider the component containing I(k), where we are writing k rather than {k}. If we choose any element a\a2... an of Y' with a G {k, k}, then the corresponding element of the component containing I(k) has all entries the same except that in coordinate i it has ai. Thus, there is an edge joining these two vertices via (i i). In a similar way, there is an edge from Y' to any component containing I (A), where A is a singleton.
In a similar manner, we can find an edge from the component containing I(k) to any component containing I(k, where I = k and we do not include the set brackets around k and I. It now is obvious that we can use edges generated by (i i) to connect all the components of Y into a single component of X.	□
Theorem 4.3. If X = Cay(Sn I S2; S) is connected, has valency at least three, and S contains only double transpositions and transpositions, then X is bipartite and Hamilton-laceable.
Proof. First we show that X is bipartite. Let A consist of the signed permutations f = a\a2 • • • an such that y(f) is an even permutation and f has an even number of negative terms, or y>(f) is an odd permutation and f has an odd number of negative terms. Let B be the remaining elements of Sn IS2. It is easy to see that if we multiply any element of A on the right by an element of S, we obtain an element of B and vice versa. We conclude that X is bipartite.
Small values of n produce some anomalous situations and we investigate them separately. When n = 2, all of the possibilities giving valency 3 are isomorphic to the cartesian product of a 4-cycle and K2. This is known to be Hamilton-laceable. When the valency is 4, the graph is isomorphic to K4,4 which is Hamilton-laceable. Hence, the result is true for
n = 2.
We cannot apply induction for the n = 3 case because the valency may be 3 and upon deleting an element from the connection set, we obtain a subgraph whose components are even length cycles. Even cycles are not Hamilton-laceable so that we must do this case separately.
Let X satisfy the hypotheses and n = 3. Because X is connected, aux(S) is connected and contains a spanning tree. The spanning tree must be a path of length 2 because n = 3. By relabelling the elements on which the group Sn I S2 acts, if necessary, we may assume the spanning tree is 123. Note that the spanning tree does not uniquely determine the connection set for X. For example, the edge 12 arises from at least one of the double transpositions (1 2)(T 2) and (1 2)(1 2) belonging to S. (Of course, both of these double transpositions could belong to S.)
42
Ars Math. Contemp. 8 (2015) 149-162
„,„ 231 321 _
,„„ 213___312 ,„„
123 ■--.— rn m------ 132
Figure 2
If the double transpositions (1 2)(T 2) and (2 3)(2 3), and the transposition (3 3) belong to S, then they generate a spanning subgraph of X isomorphic to the graph shown in Figure 2. In fact, no matter which double transpositions are chosen corresponding to the spanning tree together with either of the transposition (1 1) or (3 3), we obtain a spanning subgraph of X isomorphic to the graph in Figure 2. If we have the transposition (2 2), we obtain edges between the eight 6-cycles such that the two edges joining two fixed 6-cycles are incident with diametrically opposed vertices on the 6-cycles instead of neighboring vertices as in the graph shown in Figure 2.
The essential point is that we have two trivalent bipartite graphs of order 48 that need to be directly checked whether they are Hamilton-laceable. This may seem to be a daunting task, but as a matter of fact it is fairly straightforward.
Consider the graph in Figure 2. It suffices to find a Hamilton path from the vertex 123 to any vertex in the other part of the bipartition because X is vertex-transitive. For example, suppose you want a Hamilton path terminating at the vertex 312 in the figure. Construct a path starting with 123 that spans the 6-cycle containing 123 and terminates at 132. Continue by taking the edge to 132 followed by using all the vertices of this 6-cycle and terminating at the vertex 312. We now have a path starting at 123 and terminating at 312.
It is easy to see how to transform this starting path into a Hamilton path terminating at 312. Remove the edge joining 231 and 321 from the path and take the two edges down to the vertices 231 and 321 in another 6-cycle. Join 321 and 231 using all the vertices of that 6-cycle. It is easy to see that we can continue to delete an edge from the expanding path and move to another 6-cycle and pick up all of its vertices until reaching a Hamilton path.
The preceding technique together with Posa exchanges establishes that the graph of Figure 2 is Hamilton-laceable. The other possible isomorph is a little harder to work with, but it is still fairly easy to establish that it is Hamilton-laceable. Hence, the theorem is true
B. Alspach: Hamilton paths in Cayley graphs on Coxeter groups: I
43
for n = 3.
We continue the proof by induction on n. Let n > 4 and assume the theorem holds for n - 1. Because aux(S) is connected, it has a spanning tree T. Moreover, because T has at least two leaves, T has a leaf j such that the connection set S contains a transposition (i i) for which i = j. Relabel the elements 1,2,..., n, if necessary, so that a double transposition g satisfying y>(g) = (n - 1 n) belongs to S, where j is relabelled as n.
Now let S' denote all the elements of S that fix n. The group (S'} generated by S' is isomorphic to Sn-11 S2 by Lemma 4.2, and the Cayley graph Y = Cay(Sn-11 S2; S') is connected and bipartite. We know that Y is Hamilton-laceable by induction.
The Cayley graph X' = Cay(Sn \ S2; S') is disconnected with components isomorphic to Y. This follows because (S'} generates all signed permutations of 1,2, 3,..., n with n fixed and this is the component of X' containing the identity. If we left multiply (S'} by any element of h G Sn ^ S2, we get all the signed permutations for which n is mapped to h(n), that is, the last coordinate is h(n). Left multiplication is an automorphism of both X and X' so that all the left cosets of (S'} induce isomorphs of Y. This sets the stage for the induction proof via Lemma 3.1.
We use the components of X' to give us the partition of V(X). Let C(z) denote the component consisting of the signed permutations ending with z. If there is an edge from one part of the component C(x) to one part of the component C(y), x = y, then left multiplication by a double transposition from S' gives an edge joining the other two parts of the same two components. Thus, a crucial hypothesis of Lemma 3.1 is satisfied.
It suffices to show that there are Hamilton paths in X from 123 • • • n to every vertex of B because X is vertex-transitive. The double transposition g satisfying y>(g) = (n - 1 n) is either (n — 1 n)(n — 1 n) or (n — 1 n)(n — 1 n). We first consider the case that g = (n — 1 n)(n — 1 n).
Let x = y such that x = y. There is a signed permutation in C(x) ending yx. Right multiplication by g gives an edge from C(x) to C(y).
Let v be an arbitrary vertex in B in a component C(x) such that x = n. By Lemma 3.1 it suffices to find a Hamilton path in the quotient graph X/A from C(n) to C(x). We claim there is a sequence y1, y2,..., y2n composed of the elements 1,1,..., n, n such that y1 = n, y2n = x and j, j are never consecutive.
Letting i < n, use the sequence
n, n — 1, .. ., i +1, 1, 2,. .., n, 1, 2, .. ., i
when x = i. When x = i, we negate every term in this sequence other than the first.
When x = n, use
n, n — 1, ..., 1, 2, 1, 3,. .., n.
From the above remark, there are edges joining consecutive components corresponding to the sequence and the desired Hamilton path exists.
We have to modify the approach somewhat when x = n, that is, the target vertex v = a1a2 • • • an-1n also lies in C(n). We start with a path P from 123 • • • n to v that spans the vertices of C(n). We examine an_1.
As we traverse P backwards, find the first vertex w for which the n — 1 entry is different from an-1. In other words, the subpath P [123 • • • n, w] terminates in a vertex w whose n—1 entry is not an-1, but every vertex of the subpath P(w, a1a2 • • • n] has an-1 in coordinate n — 1. Let w' be the successor of w on P.
44
Ars Math. Contemp. 8 (2015) 149-162
Remove the edge ww' from P. The vertices wg and w'g lie in different components because they differ in coordinate n. It is easy to see how to slightly modify the preceding argument so that we obtain a path from w to w' spanning all the vertices of the remaining components. This yields a Hamilton path joining 123 • • • n and v.
The other case is g = (n n - 1)(n - 1 n). It is different because multiplying on the right by g not only switches the elements in coordinates n - 1 and n, it also changes the signs of both. However, it takes only a small modification of the above procedure to handle this case. Use the same sequences y\,y2,..., y2n, but when terminating the path spanning a left coset, stop at a vertex whose last two coordinates are y+yi. Multiplying on the right by g then takes you to a vertex in the correct left coset. This completes the proof. □
5 An Index 2 Subgroup Of Sn I S2
The groups we considered in the preceding section were the signed permutations of length n. A natural subgroup for each of these groups is the collection of signed permutations with an even number of negative terms. This group is the Coxeter group Dn. It is easy to see that Dn has index 2 in Sn l S2.
The Coxeter diagram for the group Dn is shown in Figure 3. The generator Ri, 1 < i < n — 1, is the reflection through the orthogonal complement of the vector with 1 in coordinate i, 1 in coordinate i + 1, and zeros elsewhere. The generator Rn is the reflection through the orthogonal complement of the vector with 1 in the last two coordinates and zeros elsewhere.
The first step is to decide which connection sets we are going to allow for the Cayley graphs on Dn. We shall use double transpositions as we have done for Sn l S2, but now we require a product of two transpositions that negates two coordinates, that is, a permutation
f G Sn l S2 such that f (i) = i, f (j) = j, and f fixes all other elements k, where i = j and k G {i,j}. We call such a permutation a double negator.
In order to set the stage for what follows, we examine n = 2, 3 ahead of time. The case of n = 2 is particularly simple, and not particularly edifying, because |D2| = 4. So the only Cayley graph on Dn of valency 3 is K4. It is not bipartite and certainly is Hamilton-connected.
In general, we let X = Cay(Dn; S) be a Cayley graph on Dn such that S contains only double transpositions and double negators. We again define aux(S) by letting the vertices be 1, 2,... ,n, and joining i and j with an edge if and only if there is a double transposition f G S such that y(f) = (i j).
We return to our consideration of the two smallest values of n. There is considerably more complexity when n = 3. Note that |D3| = 24.
If aux(S) is not connected, then it must have a singleton component. Without loss of
B. Alspach: Hamilton paths in Cayley graphs on Coxeter groups: I
45
generality we may assume vertex 3 is a singleton. This means that every double transposition in the connection set S fixes both 3 and 3, and double negators fix all the blocks. Thus, the block {3,3} is fixed by the group (S} generated by S. Hence, (S} is a proper subgroup of D3 which implies that X is not connected. Therefore, we see that if X is connected, then aux(S) is connected.
We are assuming that X is connected so that aux(S) contains a spanning tree. The spanning tree must be a path of length 2 because aux(S) has order 3. Without loss of generality we may assume the set on which the group D3 is acting is labelled so that the path forming the spanning tree consists of the edges 12 and 23.
We now consider possible special subgraphs of X. First, suppose the double transpositions generating the edges 12 and 23 are (1 2)(1 2) and (2 3)(2 3). These two double transpositions generate the subgraph shown in Figure 4.
123 213 231 321 312 132 >--*-•-•-* ............•
123 213 231 321 312 132 123 213 231 321 312 132 »............ »-•-•-* ............»............ »-•-•-»_____
123 213 231 321 312 132 »............ »-•-•-* ............
Figure 4
In order for X to be connected, we need either a double negator or a negative double transposition in S (where a double transposition is negative when it has the form (i j)(i j)). If we have the double negator (1 1)(2 2) in S, we obtain the trivalent spanning subgraph Y\ shown in Figure 5. The graph Y1 is not bipartite and it can be verified directly that it is Hamilton-connected.
Figure 5: The subgraph Yx
If we use the double negator (2 2)(3 3), we obtain a graph that is isomorphic to Y\. The same conclusions then follow. If instead we use the double negator (1 1)(3 3), we obtain
46
Ars Math. Contemp. 8 (2015) 149-162
the graph Y2 shown in Figure 6. The graph Y2 also is not bipartite and it can be verified directly that Y2 is Hamilton-connected.
Figure 6: The subgraph Y2
If we partition the vertices of X so that part A contains the permutations f for which ip(f) is an even permutation in S3, and part B contains the permutations f such that y(f) is an odd permutation, then the edges generated by any double transposition have one end in A and one end in B. Hence, if S contains no double negator, then X is bipartite.
Moreover, if S contains no double negator, then there must be a double transposition in S not contained in the group generated by (1 2)(T 2) and (2 3)(2 3). If we use the negative double transposition (1 2)(1 2) to connect the components of the spanning graph shown in Figure 4, we obtain the graph Y3 shown in Figure 7. This graph is bipartite and it is easy to verify that it is Hamilton-laceable.
Figure 7: The subgraph Y3
If we use the negative double transposition (2 3)(2 3), we obtain a graph isomorphic to Y3. This leaves the negative double transposition (1 3)(1 3). In this case we obtain the graph Y4 shown in Figure 8. It is bipartite and easily shown to be Hamilton-laceable.
B. Alspach: Hamilton paths in Cayley graphs on Coxeter groups: I
47
Figure 8: The subgraph Y4
It is obvious that two Cayley graphs on the same group G, with respective connection sets S' and gS'g-1 for g G G, are isomorphic via conjugation by g. Therefore, if S contains exactly one positive double transposition, or S contains no positive double transpositions, then each Cayley graph we obtain is isomorphic via conjugation to one of those we have considered above.
This completes the analysis of the case that n — 3. What we have seen is that a spanning tree of aux(S) always produces a 2-factor composed of four 6-cycles. If any double negator lies in the connection set S, then the resulting spanning trivalent subgraph is connected, not bipartite and Hamilton-connected. This implies, of course, that X is Hamilton-connected.
Continuing in this vein, if S contains no double negators, then X is bipartite and Hamilton-laceable when it is connected. The subgraph generated by any two double transpositions t1, t2, corresponding to a spanning tree, is a 2-factor composed of four 6-cycles. Any double transposition t3 g (r1, r2) results in a disconnected spanning trivalent subgraph. So for X to be connected, we need a double transposition that is not an element of the group (ti, T2).
Lemma 5.1. If X — Cay(Dn; S) is a Cayley graph on Dn such that S contains only double transpositions and double negators, then X is connected if and only if aux(S) is connected and one of the following two conditions holds:
(a)	S contains a double negator, or
(b)	S contains no double negators, but if t1,t2, ..., Tn-1 are elements of S corresponding
to a spanning tree of aux(S), then there is a t g S such that t does not belong to the group (t1, t2,..., Tn-1) generated by t1, t2, ..., Tn-1.
Moreover, X is not bipartite when n > 2 and (a) holds, whereas, X is bipartite when (b) holds.
Proof. Observe that if aux(S) is not connected, then it is obvious that X is not connected. Thus, if X is connected, then aux(S) also is connected.
If X is connected, let t1 , t2, ..., Tn-1 be the double transpositions for some spanning tree of aux( S). The group H — (t1,t2, ... ,Tn-1) is a proper subgroup of Dn by Theorem 4.1. So if S does not contain a double negator, then in order for X to be connected, there must be a double transposition t such that t G H. Hence, if X is connected, then aux(S) is connected and at least one of the two conditions holds.
48
Ars Math. Contemp. 8 (2015) 149-162
Now let aux(S) be connected and let condition (a) or (b) hold. Let ti, t2, ..., Tn-1 be as in the preceding paragraph, let X' be the subgraph of X generated by these n -1 double transpositions, and let Y be the component of X' containing 123 • • • n.
First suppose that condition (a) holds and that the double negator is (i i)(j j) The proof that X is connected closely mirrors the corresponding proof of Lemma 4.2. First, recall that I (A), where A is a subset of {1,2,..., n}, denotes the permutation which is a product of the transpositions (i i) as i runs through A and fixes all other elements. The components of X' are then the subgraphs containing the permutations I (A) as A runs over all subsets of even cardinality of {1,2,..., n}. We then show that X is connected using an argument that is the same as that used for Lemma 4.2 except that we now use two coordinates at a time instead of one. This takes care of connectivity.
We cannot claim that X is not bipartite for n = 2 because the graph may be a cycle of length 4. To conclude the proof for condition (a), we must show that X is not bipartite when S contains a double negator and n > 3 (n = 3 was done above). Let t denote the double negator (i i)(j j). We can always find a permutation f = aia2 • • • an, where aj and aj are fixed, with f G A by inverting two elements in two coordinates different from i and j if necessary.
Let f1 denote a permutation in Y such that aj G {i, i}, aj G {r, r}, r = j, and f1 G A. There is then an edge joining f1 and f1T in the left coset I (i, r)H.
In a similar manner, there is a permutation f2 in Y such that aj G {j, j}, aj G {r, r}, and f2 G A. There is then an edge joining f2 and f2T in the left coset I(j,r)H. We then find a permutation f3 in the left coset I(i, r)H belonging to A with aj G {i, i} and aj G {j, j. This is then adjacent to f3T in the left coset I (j, r)H and f3T G A. The paths joining f1 and f2 in Y, f3 and f3T in I (i, r)H, and f2T and f3T in I (j, r)H all have even lengths because the vertices all belong to A. Thus, we have an odd length cycle in X so that it is not bipartite.
When condition (b) holds, then S contains no double negators but it does contain a double transposition t not contained in the group H. The double transposition t satisfies <£>(t) = (i j) for some i = j. We know there is an element t' G H such that ^(t') = (i j) because H is isomorphic to Sn by Lemma 4.1. Moreover, Lemma 4.1 informs us that k and k are in different orbits for all k so that t' fixes all elements not in {i, i, j, j}. This implies that t't = (i i)(j j) which is a double negator. Because multiplying on the right by t' keeps one in the same left coset of H, we see that t joins the same left cosets as the preceding double negator. Therefore, X is connected by the argument for condition (a).
Note that if we let A be all the permutations f G Dn for which y>(f) is an even permutation and let B be all those for which y>(f) is an odd permutation, then any edge generated by a double transposition has one end vertex in A and one end vertex in B. Thus, if S contains no double negators, then X is bipartite.	□
Theorem 5.2. If X = Cay(Dn; S) is a connected Cayley graph of valency at least 3 on Dn, n > 2, such that S contains only double transpositions and double negators, then X is Hamilton-laceable when it is bipartite, or Hamilton-connected when it is not bipartite.
Proof. The results of this theorem have been proved for n = 2 and n = 3 earlier. We proceed by induction on n.
First consider the case that X is bipartite. As before, let
H = (ti,t2, ... ,t„_i),
B. Alspach: Hamilton paths in Cayley graphs on Coxeter groups: I
49
where t1; t2, ..., Tn-1 are the double transpositions corresponding to the edges of a spanning tree of aux(S). We know there is a double transposition t' not contained in H from Lemma 5.1. Furthermore, we saw in the proof of Lemma 5.1 that edges between the subgraphs induced on the left cosets of H join the same left cosets as do the edges generated by a double negator t = (i i)(j j). For simplicity we work with t.
As before, let A denote the elements f of (S) such that y(f) is an even permutation and let B denote the other elements of the group. Clearly, A and B are the two parts of the bipartition of X.
We know that I(L)H are the left cosets of H as L runs through all even cardinality subsets of {1,2,..., n}. If E1 and E2 are two subsets of the same even cardinality a and they have a — 1 elements in common, then there is an edge joining a vertex of I(E1)H and a vertex of I(E2)H. To see this let x, y be the two elements of E1AE2 (symmetric difference). Let f = a1a2 • • • an be an element of H so that a G {x, x} and a,j G {y, y}. Then we have I(E1)/t = I(E2)f which implies there is an edge between the left cosets I(E1)H and I(E2)H.
Now form a quotient graph by contracting each left coset to a single vertex making two vertices adjacent if there is an edge joining vertices of the corresponding left cosets. From the preceding paragraph, we see that two vertices corresponding to left cosets I(E1)H and I(E1)H, |E1| = |E2|, are adjacent if E1 and E2 have all but one element in common. Thus, all left cosets corresponding to subsets of {1, 2,..., n} of the same cardinality k induce a subgraph containing the Johnson graph J(n, k).
It is also easy to see that if E1 is a subset of E2 with |E11 = |E21 — 2, then there is an edge between the corresponding left cosets. Hence, the quotient graph contains a spanning subgraph isomorphic to QJ(n, C), where C is the collection of all even cardinality subsets of {1, 2,..., n}. This graph is Hamilton-connected by Theorem 3.2. Thus, we may employ Lemma 3.1 to easily find Hamilton path in X from 123 • • • n to any vertex of B in any left coset different from H.
If the target vertex v happens to lie in H, then there is a path from 123 • • • n to v spanning the vertices of H by induction. We then find any edge w1w2 in this path such that w1 and w2 have neighbors in different left cosets of H. We then use QJ(n, C — 0), which also is Hamilton-connected by Theorem 3.2, along with Lemma 3.1 to find a path Q from w1t' to w2t' spanning all the vertices of the remaining left cosets. We remove the edge w1w2 from the initial path spanning H and patch Q in to get a Hamilton path in X from 123 • • • n to v. This completes the bipartite case.
Now assume that S contains the double negator t = (i i)(j j). Note that <^(f) and <£>(/■t) either are both even permutations or both odd permutations. Thus, an edge generated by a double negator either has both end vertices in A or both end vertices in B.
There are two cases to consider: Either aux(S) has a spanning tree with a leaf k different from both i and j or there is no such spanning tree. We first consider the case that there is such a tree T.
Without loss of generality we assume that n is the leaf of T different from i and j. In other words, n is fixed by t. Let S' be the subset of S containing all double transpositions and double negators that fix the element n.
Because aux(S') contains a spanning tree and the double negator t, the components of Cay(Dn; S') have order 2n-2 (n — 1)! and are Hamilton-connected by induction. We now have exactly the same situation as in the proof of Theorem 4.3, namely, a subgraph each of whose components is composed of all the permutations whose last coordinate is constant.
50
Ars Math. Contemp. 8 (2015) 149-162
There is one component for each element of {1,1,..., n, n}. The double transposition corresponding to the edge of T incident with n is then used to connect the components together exactly as was done in the proof of Theorem 4.3. Hence, X is Hamilton-connected.
This leaves us with the other case, namely, there is no spanning tree with a leaf different from i and j. The preceding induction proof cannot be applied. It is not hard to see that this forces aux(S) to be a path whose end vertices are i and j.
We maintain the same notation, that is, we let S' = {n, t2, ..., Tn-1} be the double transpositions corresponding to the edges of the spanning tree, H = (S'}, X' be the subgraph Cay(Dn; S'), and Y the component of X' containing 123 • • • n. By Lemma 4.1, X' has 2n-1 components. The components are bipartite and Hamilton-laceable by Theorem 2.3. Moreover, all the components are isomorphic to Y.
For each L C {1,2,..., n}, |L| even, the action of the involution I(L) on each permutation is to negate the entries in the coordinates corresponding to the elements of L. Hence, the 2n-1 components of Cay(Dn; S') are the subgraphs induced on the left cosets I(L)H as L runs through all subsets of {1, 2,..., n} of even cardinality. As we saw earlier in this proof, the quotient graph of X obtained by contracting each left coset to a single vertex, deleting all loops, and replacing multiple edges by a single edge yields a spanning subgraph isomorphic to QJ(n, C), where C contains all even integers between 0 and n inclusive. We employ Theorem 3.2 frequently.
We define the bipartition A and B as before. Because X is vertex-transitive, it suffices to find a Hamilton path in X from 123 • • • n to any other vertex v. We shall refer to v as the target vertex.
Let v be a target vertex in the part A of any component I(L)H different from Y. Theorem 3.2 provides a Hamilton path in the quotient graph from the vertex corresponding to Y to the vertex corresponding to I(L)H. Since edges generated by t have both end vertices in either A or B, we use a (slightly) modified version of Lemma 3.1 to obtain a Hamilton path from 123 • • • n to v using the fact that there are an even number of components.
Now let the target vertex v be in part B of Y. There is a path P from 123 • • • n to v spanning the vertices of Y by Theorem 2.3. There must be two successive vertices w1, w2 on P with neighbors y1,y2 in different components I (a, b)H and I (a, c)H for some a, b, c. Considering the graph QJ(n, C'), where C' = {2,4,..., 2 |_n/2_|}, Theorem 3.2 and Lemma 3.1 imply there is a path Q from y1 to y2 spanning all the vertices of the components corresponding to C'. We then obtain a Hamilton path from 123 • • • n to v by removing the edge w1w2, adding the edges y1w1 and y2w2, and adding the path Q. Thus, X has a Hamilton path from 123 • • • n to any vertex in part B of Y.
To complete the proof of the theorem, we must find a way to circumvent the fact that the components are only Hamilton-laceable. Before introducing the trick we use, let's review the strategy we have used so far. We find a path Q spanning Y that starts at 123 • • • n and finishes at any vertex w of part B in Y. We choose w so that wt belongs to a left coset I(L)H not containing the target vertex v. We then use the fact that the graph QJ(n, C), where C contains all the even integers in {2, 3,4,..., n}, is Hamilton-connected so that we may apply Lemma 3.1 to find a path P from wt to v spanning all the left cosets of H distinct from H itself. We attach P to Q using the edge from w to wt to obtain a Hamilton path in X from 123 • • • n to v. Because the number of left cosets of H distinct from H is odd (that is, the number of vertices of Q(n, C) is odd), this works only for vertices in part A.
The trick we are about to introduce is based on removing either one or three special
B. Alspach: Hamilton paths in Cayley graphs on Coxeter groups: I
51
vertices from the QJ(n, C) graph mentioned above. If we remove a single vertex corresponding to any 2-subset, or three vertices corresponding to three 2-subsets of the form {a, b}, {a, c}, {6, c}, or three 2-subsets of the form {a, d}, {b, d}, {c, d}, then the resulting subgraph of QJ(n, C) remains Hamilton-connected. We leave this up to the reader and refer to [3] if guidance is required. The key is to prove that removing these three vertices from J(n, 2), n > 4, leaves a Hamilton-connected graph.
When the target vertex v is in part B of some component I(L)H different from Y, choose a vertex w in part B of Y such that the neighbor wt of w belongs to a left coset I (a, b)H different from I (L)H. Then choose a path Q from 123 • • • n to w that spans Y.
Suppose there is an edge xy on Q so that both it and yT lie in the same left coset C, and C does not contain v and is different from I (a, b)H. We then remove the edge xy from Q and attach the edges to it and yT. We now find a path from it to yT spanning the vertices of C. This now gives us a path Q' from 123 • • • n to w spanning the two left cosets H and C. The graph QJ(n, C) with a single vertex corresponding to a 2-subset removed is still Hamilton-connected. However, the number of left cosets left over is now even so that when we apply the strategy outlined above, we can reach a target vertex in part B as required.
Alternatively, suppose there is an edge xy of Q so that it and yT are in different left cosets Ci and C2, respectively, and a third left coset C3 so that Ci, C2, C3 are all distinct from I (L)H and I (a, b)H. If there is a path from it to yT spanning the vertices of the three left cosets C1, C2, C3, then we can replace the edge xy in Q with a path that spans the three left cosets, then we have a path from 123 • • • n to w spanning the four left cosets. The number of left cosets remaining is even and we can find a Hamilton path to a target vertex in any part B
We need to show that one of the preceding conditions holds. If the target vertex v is in a left coset I(L)H such that |L| > 2, we don't concern ourselves with designating the set L. If |L| = 2, then we let the left coset containg v be I (a, c)H. Choose w in part B of Y so that wt g I (a, b)H, where b = c.
Let Q be a path from 123 • • • n to w spanning the vertices of Y. Because n > 4, there is an element d distinct from a, b, c. If there is an edge xy of Q so that both it and yT lie in any single one of the left cosets I(c, d)H, I(b, c)H, I(b, d)H, then the first condition above holds and there is a Hamilton path from 123 • • • n to v in X.
If we cannot find an edge xy such that it and yT lie in the same left coset, we need to examine aux(S) with more care. We know aux(S) is a path with end vertices i and j with the double negator t = (i i)(j j) joining the left cosets. Note that any double transposition in S alters at most one of the entries in coordinates i and j. Hence, if x and y are adjacent vertices of Y, then it and yT either lie in the same left coset or lie in different left cosets I(L1 )H and I(L2)H such that |L11 = |L2| = 2, and L1 and L2 have one element in common.
The number of edges from Y to a fixed coset I(L)H, where |L| = 2, is 2(n - 2)! which is at least 4 because n > 4. Hence, there is an internal vertex x of Q such that it g I(c, d)H, where d is distinct from a, b and c. Consider the predecessor y of x on Q.
If yT g I (c, d)H, we are done. If yT g I (a, d)H, then the three left cosets I (a, d)H, I(b, d)H, I(c, d)H do the job. If yT g I(b, d)H, then the three left cosets I(b, d)H, I(c, d)H, I(b, c)H do the job. If yT lies in I(b, c)H, we also easily find three left cosets that work.
In fact, the only left coset that is bad for yT is I (a, c)H. But if yT lies in the left coset
52
Ars Math. Contemp. 8 (2015) 149-162
I (a, c)H, then the successor of x on Q, call it z, cannot have zt in I (a, c)H because this forces the edges yx followed by xz to be generated by the same double transposition because aux(S) is a path. However, double transpositions are involutions so that we cannot use them consecutively when generating distinct vertices. Thus, xt and zt must lie in left cosets satisfying one of the conditions above.
This leaves us with the target vertex being in part A of Y as the only missing case. Suppose that v lies in part A of Y and vt g I (a, b)H. Let w be in part B of Y such that wt lies in I (a, b)H as well. Let Q be a path from 123 • • • n to w spanning the vertices of Y.
The vertex v is an internal vertex of Q. Remove the edge between the predecessor u of v and v. This breaks Q into a subpath Qi from 123 • • • n to u, and a subpath Q2 from v to w. Because u is adjacent to v and by changing the labels, if necessary, we may assume that ut G I (a, e)H for some e.
If e = c, then find a vertex z internal to either Q1 or Q2 such that zt g I(b, d)H. Just as above, one of the two neighbors of z on Q allows us to use either one or three left cosets to augment either Q1 or Q2. We then cover all the remaining cosets using a path with wt and ut as the end vertices as before because there are an even number of cosets unused. We have the desired Hamilton path.
If e = d a similar argument works. If e G {b, c, d} it is even simpler because we have a new symbol to work with. However, it is possible that e = b so that wt and ut lie in the same left coset I (a, b)H.
We now have the situation that Q1 has been extended to part B of the left coset I (a, b)H via the edge to ut. Similarly, Q2 has been extended to part B of the same left coset via the edge to vt . Now choose a vertex u1 in part A of I (a, b)H whose i, j entries are disjoint from the i, j entries of ut . Then choose a path Q' from u1 to wt that spans the vertices of I (a, b)H. The successor u2 of ut then is adjacent to a vertex in a different left coset of H than is u1. This allows us to obtain a Hamilton path from 123 • • • n to v in X and completes the proof.	□
Acknowledgements. The author wishes to thank Adam Piggot for his enlightening lessons about Coxeter groups. I also thank Eva Czabarka and Laszlo Szekele for bringing the connection between Cayley graphs on Sn I S2 and genome switching to my attention.
References
[1]	S. Akers, D. Harel and B. Krishnamurthy, The star graph: attractive alternative to the n-cube, in: Interconnection Networks For High-Performance Parallel Computers, IEEE Computer Society Press, Los Alamitos, 1994, 145-152.
[2]	B. Alspach, The search for long paths and cycles in vertex-transitive graphs and digraphs, in: Kevin L. McAvaney (ed.), Combinatorial Mathematics VIII, Lecture Notes in Mathematics 884, Springer-Verlag, Berlin, 1981, 14-22.
[3]	B. Alspach, Johnson graphs are Hamilton-connected, Ars. Math. Contemp. 6 (2013), 21-23.
[4]	B. Alspach, C. C. Chen, and M. Dean, Hamilton paths in Cayley graphs on generalized dihedral groups, Ars Math. Contemp. 3 (2010), 29-47.
[5]	B. Alspach and C.-Q. Zhang, Hamilton cycles in cubic Cayley graphs on dihedral groups, Ars Combin. 28 (1989), 101-108.
B. Alspach: Hamilton paths in Cayley graphs on Coxeter groups: I
53
[6]	A. Altshuler, Hamiltonian circuits in some maps on the torus, Discrete Math. 1 (1972), 299314.
[7]	T. Araki, Hyper Hamiltonian Laceability of Cayley Graphs Generated by Transpositions, Networks 48 (2006), 121-124.
[8]	J. H. Conway, N. J. A. Sloane and A. R. Wilks, Gray Codes For Reflection Groups, Graphs and Combin 5 (1989), 315-325.
[9]	S. Curran and J. A. Gallian, Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey. Discrete Math. 156 (1996), 1-18.
[10]	S. J. Curran, D. Morris and J. Morris, Cayley graphs of order 16p are hamiltonian, Ars Math. Contemp. 5 (2012), 185-211.
[11]	E. Ghaderpour and D. Morris, Cayley graphs on nilpotent groups with cyclic commutator subgroup are hamiltonian, Ars Math. Contemp. 7 (2014), 55-72.
[12]	S. Hannenhali and P. A. Pevzner, Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, Journal of the ACM 46 (1999), 1-27.
[13]	S. Johnson, Generation of permutations by adjacent transpositions, Math. Comput. 17 (1963), 282-285.
[14]	K. Kutnar, D. Marusic, D. Morris, J. Morris and P. Sparl, Hamiltonian cycles in Cayley graphs of small order, Ars Math. Contemp. 5 (2012), 27-71.
[15]	L. Lovasz, Problem 11, Combinatorial Structures And Their Applications, Gordon and Breach, New York, 1970, 243-246.
[16]	H. Trotter, Algorithm 115, PERM., Commun. ACM 5 (1962), 434-435.
[17]	D. Witte and J. A. Gallian, A survey: Hamiltonian cycles in Cayley graphs. Discrete Math. 51 (1984), 293-304.