Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 3 (2010) 29–47
Hamilton paths in Cayley graphs on
generalized dihedral groups
Brian Alspach
School of Mathematical and Physical Sciences, University of Newcastle
Callaghan, NSW 2308, Australia
C. C. Chen
Integrated Decision Systems Consultancy Pte Ltd, 06–06
Pacific Tech Centre, Singapore 159303
Matthew Dean
Mathematics Department, The University of Queensland
St Lucia, Queensland 4072, Australia
Received 17 March 2009, accepted 25 January 2010, published online 1 February 2010
Abstract
We investigate the existence of Hamilton paths in connected Cayley graphs on gener-
alized dihedral groups. In particular, we show that a connected Cayley graph of valency at
least three on a generalized dihedral group, whose order is divisible by four, is Hamilton-
connected, unless it is bipartite, in which case it is Hamilton-laceable.
Keywords: Hamilton-connected, Hamilton-laceable, Cayley graph, generalized dihedral group, hon-
eycomb toroidal graph
Math. Subj. Class.: 05C25, 05C70
1 Introduction
A family of trivalent vertex-transitive graphs that have garnered attention over the last
thirty-five years have been called brick products in [1, 2, 5], honeycomb tori in [8, 9, 12, 13,
14, 15], honeycomb toroidal graphs in [3], and hexagonal toroidal embeddings in [6, 11].
Altshuler [6] studied them when he was considering Hamilton cycles in graphs embedded
E-mail addresses: brian.alspach@newcastle.edu.au (Brian Alspach), ccchen@idsc.com.sg (C. C. Chen),
mdean@uq.edu.au (Matthew Dean)
Copyright c© 2010 DMFA Slovenije
30 Ars Math. Contemp. 3 (2010) 29–47
in the torus. He was unable to prove that all of them are hamiltonian. That all are hamil-
tonian was first proven in [5] and independently proven in [15]. Hamilton paths in these
graphs were considered in [1, 2].
Recently [3] it was shown that these trivalent graphs are Cayley graphs on generalized
dihedral groups. In this paper we study Hamilton paths in the latter family of graphs.
The results obtained, of course, then apply to the subfamily of honeycomb toroidal graphs
mentioned above.
We now give some definitions to set the stage for the development of the material.
Definition 1.1. Let G denote a finite group and let S be a subset of G satisfying
1. 1 6∈ S, where 1 denotes the identity of G, and
2. s ∈ S implies s−1 ∈ S.
The Cayley graph Cay(G;S) on G with connection set S has the elements of G as its
vertices and an edge joining g to gs for all g ∈ G and s ∈ S.
We emphasize that we consider only finite groups and finite graphs in this paper. There
are two families of Cayley graphs we consider. They arise from the family of dihedral
groups and the family of generalized dihedral groups. Even though the former is a subfam-
ily of the latter, we distinguish the dihedral groups because they have such a rich history on
their own.
Definition 1.2. The dihedral group Dn is the group of order 2n with generators ρ and τ
that satisfy
ρn = τ2 = 1 and τρτ = ρ−1.
Definition 1.3. Let H be a finite abelian group. The generalized dihedral group DH is the
group of order 2|H| generated by H and τ where τ 6∈ H , τ2 = 1, and τhτ = h−1 for all
h ∈ H .
Definition 1.4. The honeycomb toroidal graph HTG(m, 2n, s), where m+ s is even, m =
1, and n = 2, is the trivalent graph defined as follows. It has vertex set {ui,j : 0 5 i 5
m− 1, 0 5 j 5 2n− 1}, and it has the following edges where all the arithmetic is carried
out on the subscripts modulo m or 2n as appropriate. For each i ∈ {0, 1, . . . ,m− 1}, ui,j
is adjacent to ui,j−1 and ui,j+1. For each even i ∈ {0, 1, . . . ,m − 2}, there is an edge
from ui,j to ui+1,j for all odd j. For each odd i ∈ {0, 1, . . . ,m− 2}, there is an edge from
ui,j to ui+1,j for all even j. If m− 1 is even, there is an edge from um−1,j to u0,j+s for all
odd j. If m− 1 is odd, there is an edge from um−1,j to u0,j+s for all even j.
We are not using the terminology generalized honeycomb tori because a torus is a sur-
face and even though the graphs embed on the torus, we think it better to not treat the graph
itself as a surface. Instead, we use the terminology honeycomb toroidal graphs. There
is some nomenclature we use throughout this paper for honeycomb toroidal graphs that
should be mentioned now. Edges that belong to the 2n-cycles induced on the vertices ui,j ,
with i fixed, are called vertical edges. Edges of the form ui,jui+1,j , where 0 5 i 5 m− 2,
are called flat edges. Edges joining vertices of the column indexed 0 and the column in-
dexed m− 1 are called jump edges. The latter edges are said to have jump s.
The following result was proven in [3].
B. Alspach et al.: Hamilton paths in Cayley graphs on generalized dihedral groups 31
Theorem 1.5. The honeycomb toroidal graph HTG(m, 2n, s) is a Cayley graph on the
generalized dihedral group DH , where H is either a cyclic group or a direct product of
two cyclic groups.
Recall that a graphX is Hamilton-connected if, for every pair of vertices u, v ∈ V (X),
there is a Hamilton path whose terminal vertices are u and v. Similarly, a bipartite graph
with parts A and B is Hamilton-laceable if, for all vertices u ∈ A and v ∈ B, there is a
Hamilton path whose terminal vertices are u and v. The latter, of course, forces |A| = |B|
to be the case.
Definition 1.6. We say that a familyF of graphs isH∗-connected when every non-bipartite
graph in F is Hamilton-connected and every bipartite graph in F is Hamilton-laceable.
The most celebrated theorem relating Cayley graphs andH∗-connectivity is the follow-
ing theorem of Chen and Quimpo [7].
Theorem 1.7. The family of connected Cayley graphs of valency three or more on abelian
groups is an H∗-connected family.
Theorem 1.7 has been extended to the family of connected Cayley graphs of valency
three or more on hamiltonian groups [4]. In this paper we consider the extension to gener-
alized dihedral groups. The main result is the following theorem.
Theorem 1.8. The family of connected Cayley graphs of valency at least 3 on generalized
dihedral groups, whose orders are divisible by 4, is an H∗-connected family.
Outline of proof. The proof of Theorem 1.8 is long, indeed, the rest of the paper,
except two short corollaries at the end, consists of the proof. Consequently, a few words
about the proof are in order. Given a Cayley graph X = Cay(DH ;S) on the generalized
dihedral group DH , throughout the paper we let S1 denote S ∩H , S2 denote S ∩Hτ , X1
denote the subgraph induced on H by X , and X2 denote the subgraph induced on Hτ by
X .
Of course,X1 andX2 are isomorphic Cayley graphs on abelian groups so that Theorem
1.7 may be applied for these subgraphs. It should be no surprise then that the further we
are from being able to apply Theorem 1.7, the more work we must perform. Hence, the
proof has three basic cases: S1 = ∅, |S1| = 1, and |S1| = 2.
There are several techniques that are used in the three cases and these are presented
as separate lemmas in Section 2 in order to improve the exposition for the three cases
and to avoid repetition for those techniques which are applied more than once. Section 3
addresses honeycomb toroidal graphs. They form the basis for establishing Theorem 1.8
when S1 = ∅.
Section 4 then contains the proof of the theorem. The case S = ∅ is completed via
induction on |S2|. The case |S1| = 1 takes some work too but not as much as the preceding
case. The case |S1| = 2 is fairly easy because of the power of Theorem 1.7 and techniques
developed in Section 2.
2 Basic toolkit
We now present some useful lemmas as described above.
32 Ars Math. Contemp. 3 (2010) 29–47
Definition 2.1. Let P = u0u1 · · ·uk be a path of length k in some graph. If uk is adjacent
to a vertex ur on P , where ur 6= uk−1, then deleting the edge urur+1 from P and inserting
the edge joining ur to uk is called a Posa exchange. We say that we have performed a Posa
exchange on P using the edge ukur. Note that we obtain a path from u0 to ur+1 spanning
the same set of vertices as P . In particular, when P is a Hamilton path, we obtain another
Hamilton path with one end vertex altered.
There is a structural property of the Cayley graphs under discussion that is used fre-
quently. It is embodied in the next lemma, but before embarking on the proof, there are
some useful observations to be made.
Given a Cayley graph on some group G, left multiplication by a group element from
G is a graph automorphism. From this we see that the subgraphs induced by a Cayley
graph on distinct left cosets of a subgroup of G are isomorphic. Thus, in general, for
subgraph properties in Cayley graphs it is more convenient to think in terms of left cosets
when a subgroup is involved. On the other hand, given a vertex in a Cayley graph its
neighbors are determined by right multiplication. So getting from one vertex to another is
more conveniently thought of in terms of right multiplication. This makes right cosets also
useful when thinking about various properties of Cayley graphs.
Lemma 2.2. Let X be a Cayley graph on a generalized dihedral group DH , H ′ be a
subgroup ofH , and Y1 and Y2 be the subgraphs induced byX on two distinct cosets ofH ′.
If there is an edge from the vertex g1 ∈ Y1 to g1s ∈ Y2, then the element s ∈ S generates a
perfect matching between Y1 and Y2, that is, for every g ∈ Y1 the vertex gs ∈ Y2.
Proof. The subgroup H ′ is normal in DH so that gH ′ = H ′g for all g ∈ DH , that is, left
and right cosets of H ′ are the same. That is why the statement of the theorem only refers
to cosets of H ′. Let Y ′1 be the subgraph induced on H
′ by X .
Consider a vertex labelled h′ in Y ′1 . Consider any element s in the connection set not
belonging to H ′. Then the vertex labelled h′ is adjacent to the vertex labelled h′s which
belongs to the coset H ′s. Thus, if we multiply every element of H ′ on the right by s,
we obtain H ′s. That is, the element s in the connection set generates a perfect matching
between the vertices labelled with elements of H ′ and those labelled with elements of H ′s.
The result follows because left multiplication is a graph automorphism.
Lemma 2.3. Let X be a bipartite graph containing vertex-disjoint bipartite subgraphs Y0,
Y1, . . . , Yt, each of order at least 4, with respective bipartitions (A0, B0), (A1, B1), . . . ,
(At, Bt) and which together span X . If each of the bipartite subgraphs is Hamilton-
laceable and there is a perfect matching joining the vertices of Ai to the vertices of Bi+1
for i = 0, 1, . . . , t, where we take Bt+1 to be B0, then X is Hamilton-laceable.
Proof. Choose an arbitrary vertex u ∈ A0. We want to show there is a Hamilton path from
u to any vertex v belonging to someBj . First let v ∈ B0. By hypothesis there is a Hamilton
path P0 in Y0 from u to v. Let uv0 be the first edge of P0. Remove this edge from P0 and
build a new path starting at u by using the perfect matching edge from u to v1 ∈ B1. Then
add a Hamilton path P1 in Y1 from v1 to some u1 ∈ A1. Extend this path by adding the
matching edge from u1 to v2 ∈ B2. Now extend by adding a Hamilton path in Y2 from v2
to some u2 ∈ A2. Continue in this way until reaching a vertex vt ∈ Bt. Let ut ∈ At be
the neighbor of v0 in the perfect matching between At and B0. Extend the path by adding
a Hamilton path from vt to ut in Yt. Now add the edge from ut to v0. We have replaced
B. Alspach et al.: Hamilton paths in Cayley graphs on generalized dihedral groups 33
the edge uv0 by a path that uses all vertices of X not in Y0. Thus, we have a Hamilton path
in X from u to v.
If v ∈ B1, then it is easy to find a Hamilton path from u to v by taking a Hamilton path
in Y0 from u to some v0 ∈ B0, then adding the matching edge into At, and then adding a
Hamilton path using all the vertices in Yt. Then move into Yt−1 and continue around to Y1.
Because we enter Y1 at a vertex of A1, it is easy to complete to a Hamilton path from u to
v.
Let v ∈ Bi with i 6∈ {0, 1}. First choose a Hamilton path P ′ in Y0 from u to some
v0,0 ∈ B0. Let v0,1u0v0,0 be the last two edges of P ′. Let P be the subpath of P ′ from u
to v0,1 and let Q be the path consisting of the edge u0v0,0. Note that P and Q use all the
vertices of Y0.
We extend Q first. Add the matching edge from u0 to its neighbor v1 ∈ B1. If v ∈ B2,
do not extend Q any further in this direction at this time. If v 6∈ B2, then let u1 ∈ A1 and
extend Q by adding a Hamilton path in X1 from v1 to u1. Continue extending Q in this
way so that the extension of Q in this direction uses all vertices of Y1, Y2, . . . , Yi−2 and
terminates with the matching edge from the last vertex of Q in Ai−2 to a vertex vi−1 ∈
Bi−1.
Extend both P and Q in the other direction as follows. Extend them into Yt by adding
the matching edges from v0,1 and v0,0 to ut,1 and ut,0, respectively, in At. If v 6∈ Bt, then
consider any Hamilton path in Yt starting with ut,0. Let vt,0 be the predecessor of ut,1 on
this Hamilton path. Now extend Q by adding the subpath from ut,0 to vt,0 and extend P
by adding the subpath from ut,1 to the terminal vertex vt,1. The extended paths use all the
vertices of Yt. Continue extending P andQ through Yt−1, Yt−2, and so on until completing
Yi+1.
Let the terminal vertices of the extended paths Q and P in Yi+1 be vi+1,0 and vi+1,1,
respectively. Add on the matching edges from both into Ai. Let the terminal vertices now
be ui,0 and ui,1, respectively. We now describe how to combine everything into a single
Hamilton path from u to v. This also works when v ∈ Bt.
Let R be a Hamilton path in Yi from ui,1 to v. As we traverse R from ui,1 to v, let v′
be the predecessor of ui,0. Now add the subpath of R from ui,0 to v to Q, and the subpath
from ui,1 to v′ to P . Let ui−1 be the vertex of Ai−1 adjacent to v′ by a matching edge. To
the other end of Q add a Hamilton path in Yi−1 from vi−1 to ui−1, and the matching edge
to v′. The resulting path is a Hamilton path in X joining u and v. Because the bipartite
subgraphs are joined in a cyclic fashion, the preceding argument works for any u and v in
different parts of the bipartition of X .
Lemma 2.4. Let X be a vertex-transitive graph containing a spanning subgraph Y that
consists of a perfect matching of t edges e0, e1, . . . , et−1 such that ei is joined to ei+1 by a
2-matching for i = 0, 1, . . . , t − 1, where et = e0. If X is bipartite, then X is Hamilton-
laceable, and if X is not bipartite, then X is Hamilton-connected.
Proof. The edges e0, e1, . . . , et−1 are joined by successive 2-matchings and we may as-
sume the end vertices of ei are labelled with ui and vi, respectively, so that ui is adjacent
to ui+1 and vi is adjacent to vi+1 for i = 0, 1, . . . , t − 2. The key to the proof is the
2-matching between et−1 and e0.
Let Y be the spanning subgraph made up of the edges e0, e1, . . . , et−1 and the 2-
matchings joining ei to ei+1, i = 0, 1, . . . , t− 1. If u0ut and v0vt are edges of Y , then Y
is isomorphic to the cartesian product of a t-cycle and K2. On the other hand, if u0vt and
34 Ars Math. Contemp. 3 (2010) 29–47
v0ut are edges of Y , then Y is isomorphic to the circulant graph of order 2t with connec-
tion set {±1, t}. Both possible spanning graphs are Cayley graphs on abelian groups so
that X is Hamilton-laceable by Theorem 1.7.
Moreover, when Y is isomorphic to the cartesian product of a t-cycle and K2, Y is
not bipartite if and only if t is odd. When Y is isomorphic to the circulant graph of order
2t with connection set {±1, t}, Y is not bipartite if and only if t is even. Whenever Y is
not bipartite, it is Hamilton-connected by Theorem 1.7. This implies X itself is Hamilton-
connected.
The only situation not covered is when Y is bipartite but X itself is not bipartite. The
bipartition (A,B) of V (Y ) is uniquely determined because Y is connected. There must be
an edge of X joining two vertices in the same part because X is not bipartite. Because of
the cyclic labelling, we may assume there is an edge joining u0 to either ui, i even, or vj ,
j odd.
Suppose there is an edge from u0 to ui with i even. Consider uk, where k is odd and
k < i. Start a path
u1u2 · · ·uk−1vk−1vk−2 · · · v1v0u0.
Then add the edge from u0 to ui and continue to ut−1 using all vertices ui, ui+1, . . . , ut−1.
Now add the edge to vt−1 and work back down from vt−1 to vi−1. Because both k and
i− 1 are odd, there are an odd number of matching edges between ek and ei−1, inclusive,
so that it is easy to jump back and forth along successive matching edges until terminating
at uk.
In a similar manner it is easy to find Hamilton paths from u1 to all other vertices in the
same part as u1. A similar argument works when u0 is adjacent to some vj , j odd. Thus,
given that there is an edge of X between two vertices in the same part, then there exists
a vertex that has Hamilton paths from it to any other vertex in X . This implies that X is
Hamilton-connected because it is vertex-transitive.
Lemma 2.5. Let X be a graph and Y be a spanning subgraph of X . Suppose Y consists
of vertex-disjoint subgraphs Y0, Y1, . . . , Yt such that each of them is Hamilton-connected
and has order at least 3, and they are joined together in one of the following two ways.
Either
• Yi is joined to Yi+1 by a perfect matching for i = 0, 1, . . . , t− 1, or
• each Yi has a partition (Ai, Bi) such that |Ai| = |Bi| and Ai is joined by a perfect
matching to Bi+1 for i = 0, 1, . . . , t, where Bt+1 = B0.
Then the graph X is Hamilton-connected.
Proof. First assume that Yi is joined to Yi+1 by a perfect matching for i = 0, 1, . . . , t− 1.
Let u, v be two arbitrary vertices of X , where u ∈ Yj and v ∈ Yk. Without loss of
generality, we may assume that j 5 k.
It is easy to find a path from u to v spanning the vertices of Yj ∪ Yj+1 ∪ · · · ∪ Yk. We
do this by taking a path spanning Yj from u and terminating at v if j = i, or terminating at
a u′ ∈ Yj such that the matching edge from u′ to Yj+1 is not incident with v. This is easy
to do because there are at least three vertices in each Yi. We then extend the path through
Yj+1 via the matching edge from u′.
Once we have a path from u to v spanning the vertices of Yj ∪ Yj+1 ∪ · · · ∪ Yk,
we extend it to a Hamilton path with u and v as terminal vertices by removing an edge in
B. Alspach et al.: Hamilton paths in Cayley graphs on generalized dihedral groups 35
Yj and adding the two matching edges into Yj−1 and then joining the new vertices with a
path spanning Yj−1. We may continue in this way until we have included all vertices of Yi,
i < j. We can include all the vertices from Yi with i > k in the same way. We have shown
that the graph Y is Hamilton-connected because u and v are arbitrary.
Move to the case that Yi has a partition (Ai, Bi) as described earlier, i = 0, 1, . . . , t.
Because of the way the subgraphs are joined, it suffices to find a Hamilton path from an
arbitrary vertex u ∈ A0 to any other vertex. So let u be an arbitrary vertex of A0. Let
v ∈ Y0, v 6= u, and let P be a Hamilton path in Y0 joining u and v. There must be an edge
u0v0 on P such that as P is traversed from u to v, the edge is traversed from u0 to v0, and
u0 ∈ A0 and v0 ∈ B0. Let v1 be the vertex of B1 adjacent to u0 by a matching edge, and
let ut be the vertex of At adjacent to v0 by a matching edge. Remove the edge u0v0 from
P and instead go from u0 to v1. Then extend that subpath by adding on a Hamilton path
in Y1 from v1 to some u1 ∈ A1. Then add on the matching edge from u1 to v2 in B2. It
is easy to see how we continue this until we reach ut ∈ At. We then add on the matching
edge to v0 at which point we have a Hamilton path from u to v.
If v ∈ Y1, then we take a Hamilton path in Y0 from u to some v0 ∈ B0. We then extend
it by adding the matching edge from v0 to a vertex in At. We then extend it by taking a
Hamilton path in Yt. We work back through successive Yi subgraphs until reachingA1. We
just make certain that we enter A1 at a vertex different from v. We then add on a Hamilton
path terminating at v.
If v ∈ Yi, i 6∈ {0, 1}, then take a Hamilton path in Y0 from u to some u0 ∈ A0.
Extend it by taking the matching edge from u0 to some v1 ∈ B1. Next extend it by taking
a Hamilton path in Y1 from v1 to some u1 ∈ A1. Then add the matching edge from u1
into B2. Keep doing this until we have a path from u to v that uses all the vertices of
Y0 ∪ Y1 ∪ · · · ∪ Yi.
If i = t, we have a Hamilton path connecting u and v. If i < t, we extend the path as
follows. Because u, u0 ∈ A0 and |A0| = |B0|, there must be an edge of the form ww′ in
the path, where both w,w′ ∈ B0. Remove this edge from the path and add on the matching
edges from w,w′ to x, x′ inAt. Then join them by a Hamilton path in Yt between x and x′.
We can keep repeating this until we have a Hamilton path joining u and v. This completes
the proof.
The following two lemmas are based on key ideas used by Chen and Quimpo in their
proof of Theorem 1.7 and is related to the first part of Lemma 2.5
Lemma 2.6. The cartesian product Pn2K2, where Pn denotes the path of order n, has the
property that if u is any corner vertex—a vertex of valency 2—and v is any vertex whose
distance from u is odd, then there is a Hamilton path in Pn2K2 joining u and v.
Proof. The proof is trivial.
Lemma 2.7. The cartesian product Pn2Cm of a path of order n, n = 2, and a cycle of
order m, m = 3, is Hamilton-laceable when m is even and Hamilton-connected when m
is odd.
Proof. The graph P22Cm is a Cayley graph on an abelian group so that Theorem 1.7
establishes the result when n = 2. Let n > 2 and assume the result holds for n − 1. Let
u and v be arbitrary vertices in Pn2Cm, where they are in different parts of the bipartition
36 Ars Math. Contemp. 3 (2010) 29–47
when m is even. Refer to the cycles corresponding to a fixed vertex of Pn as columns (we
are thinking of drawing the graph in the usual way with cartesian coordinates).
If neither u nor v lie in the n-th column, there is a path Q spanning the vertices of
the first n − 1 columns whose terminal vertices are u and v by induction. The path Q
must use an edge un−2,tun−2,t+1 from that column because m = 3. Remove the edge
un−2,tun−2,t+1 fromQ, add the edges un−2,tun−1,t and un−2,t+1un−1,t+1, and then con-
nect the two vertices of valency 1 by passing through all the vertices of the n-th column.
We now have a Hamilton path whose terminal vertices are u and v.
If exactly one of the vertices lies in the n-th column, say u, then use induction to get a
path from v, spanning the first n−1 columns, that terminates at the vertex in column n−1
that is adjacent to one of neighbors of u in the n-th column. It is obvious how to extend the
path to a Hamilton path with terminal vertices u and v.
Similarly, if both u and v lie in the n-th column, use induction to get a path from u to v
that spans the last n− 1 columns. Extend it to a Hamilton path by removing an edge from
the second column and picking up all the vertices of the first column.
Represent Pn2Cm with cartesian coordinates in the usual way, that is, the vertices are
labelled {ui,j : 0 5 i 5 n−1, 0 5 j 5 m−1}, with edges joining ui,j to ui,j−1 and ui,j+1
for all i, j, and an edge from ui,j to ui+1,j for all i 6= n−1 and all j. LetM(i, k, d) denote
the m-matching formed by the edges ui,jui+k,j+d, where k > 0, i + k < n, 0 5 d < m
and j + d is reduced modulo m. Note that M(i, 1, 0), as i runs from 0 through n − 2, are
the matching edges currently joining the column cycles.
Lemma 2.8. Let Pn2Cm be the cartesian product of the path of order n and cycle of order
m, where n > 1, m is even, and m = 4. If X is the graph obtained by adding the edges of
the m-matching M(i, k, d), where both k and d are odd, to Pn2Cm, then for every vertex
v ∈ X such that v 6= ui,0, there is a Hamilton path in X whose terminal vertices are ui,0
and v.
Proof. The subgraph Y induced on columns i, i + 1, . . . , i + k is isomorphic to a Cayley
graph on an abelian group as observed in [10]. The subgraph Y is not bipartite so that it is
Hamilton-connected by Theorem 1.7.
We’ll refer to v as the target vertex. If v lies in Y , then there is a Hamilton path spanning
Y whose terminal vertices are ui,0 and v. The path must use an edge in column i and an
edge in column i + k. Remove the two edges and take the edges into columns i − 1 and
columns i + k + 1, respectively. It is then easy to connect the end vertices of these edges
with paths spanning columns 0, 1, . . . , i− 1 and columns i+ k + 1, . . . , n− 1. This gives
us a Hamilton path from ui,0 to v in the original graph.
It is a simple matter to find the appropriate Hamilton path if the target vertex is outside
of Y by exploiting the fact that Y is Hamilton-connected.
Lemma 2.9. If X is a connected Cayley graph on the generalized dihedral group DH so
that every element of the connection set lies in Hτ , then X has a Hamilton path.
Proof. Let S denote the connection set. If |S| = 1, then X must be K2 which has a
Hamilton path. If |S| = 2, then X itself must be a Hamilton cycle which certainly contains
a Hamilton path. We proceed by induction and let |S| = 3.
B. Alspach et al.: Hamilton paths in Cayley graphs on generalized dihedral groups 37
Remove an arbitrary element s from S. If the subgraph Cay(DH : S−s) is connected,
then it has a Hamilton path by induction. If Cay(DH : S − s) is not connected, then
each component contains a Hamilton path by induction. The element s cyclically joins
the components Y1, Y2, . . . , Yt, where we may assume that s joins vertices of Yi ∩ H to
vertices of Yi+1 ∩ Hτ . Consider a Hamilton path in Yt with one terminal vertex vt ∈ Hτ .
Let ut−1 ∈ Yt−1 be adjacent to vt via an s-edge. Because the components themselves are
vertex-transitive, there is a Hamilton path in Yt−1 with ut−1 as a terminal vertex. We then
join these two paths via the s-edge and get a path spanning Yt−1 ∪ Xt. We continue this
way until we obtain a Hamilton path.
3 Honeycomb toroidal graphs
In this section we study Hamilton paths in honeycomb toroidal graphs.
Definition 3.1. A Hamilton path from u0,0 to u0,j in HTG(m, 2n, s) is called twisted if
the edge incident with u0,0 is a jump edge and the edge incident with u0,j is a flat edge.
The next lemma gives us a tool for going from solutions for particular honeycomb
toroidal graphs to solutions for a much wider class of honeycomb toroidal graphs. Some
observations about Hamilton paths in honeycomb toroidal graphs are in order. If we have
a Hamilton path P from u0,0 to some vertex v and there is a flat edge from ui−1,j to ui,j
in P , then there must be a flat edge or jump edge incident with ui,j+1 or ui,j−1 unless one
of these vertices is the other terminal vertex of P and it lies in the last column. The point
is that flat edges in a Hamilton path force other flat edges or jump edges also to be in the
path with the exception of very special situations.
Lemma 3.2. If there is a Hamilton path from u0,0 to u1,j in HTG(2, 2n, s) that uses both
flat edges and jump edges, then there is a Hamilton path from u0,0 to ui,j in HTG(m, 2n, s)
for all odd i satisfying 0 < i < m and all even m = 2. Similarly, if there is a non-twisted
Hamilton path from u0,0 to u0,j in HTG(2, 2n, s) that uses both flat edges and jump edges,
then there is a Hamilton path from u0,0 to ui,j in HTG(m, 2n, s) for all even i satisfying
0 5 i < m and all even m = 2.
Proof. If s = 0 and m = 2, the jump is zero and flat edges and jump edges look the same.
However, in this case we still distinguish between them. Edges joining u0,ju1,j are flat
when j is odd and jump edges when j is even. With this in mind, all that follows works for
this special case too.
The idea behind the proof is to show that we can take a Hamilton path in HTG(m, 2n, s)
and obtain a Hamilton path in HTG(m + 2, 2n, s) with appropriate end vertices. Sup-
pose we have a Hamilton path P from u0,0 to ui,j in HTG(m, 2n, s), i > 0, and that
u0,k1u1,k1 , u0,k2u1,k2 , . . . , u0,ktu1,kt , 0 < k1 < k2 < · · · < kt 5 2n − 1, are the flat
edges of P between the columns indexed by 0 and 1, respectively (there must be at least
one flat edge). We insert two new columns between the columns indexed by 0 and 1 which
we temporarily index with α and β from left to right. Replace the flat edge u0,k1u1,k1 with
the path
u0,k1uα,k1uα,k1+1 · · ·uα,k2−1uβ,k2−1uβ,k2−2 · · ·uβ,k1u1,k1 .
We then do the same for each flat edge, that is, we work from the row index of the flat edge
up to one less than the row index of the next (in cyclic order modulo 2n) flat edge, and
obtain a Hamilton path with one terminal vertex being u0,0 and two new columns inserted
38 Ars Math. Contemp. 3 (2010) 29–47
t t
t tt t
t t t t
t t t tt t t t
=⇒
Figure 1: Inserting two new columns.
to the left of the other terminal vertex. Upon reindexing the columns, we have a Hamilton
path from u0,0 to ui+2,j in HTG(m + 2, 2n, s). (See Figure 1 for a schematic of how the
procedure works.)
If we have a Hamilton path P from u0,0 to ui,j in HTG(m, 2n, s) and i < m− 1, then
we can insert two columns to the right of the column indexed i by using the flat edges of P
between the columns indexed m− 2 and m− 1. Hence, there is a Hamilton path from u0,0
to ui,j in HTG(m+ 2, 2n, s).
There are two special cases we must consider. Suppose there is a Hamilton path P from
u0,0 to um−1,j in HTG(m, 2n, s) and we want a Hamilton path in HTG(m+2, 2n, s) from
u0,0 to um−1,j . Thus, we want to insert two columns to the right of the column indexed
m − 1 in HTG(m, 2n, s) while keeping the terminal vertex of a new Hamilton path in
the same column. We use jump edges to do this. Let um−1,k1 , um−1,k2 , . . . , um−1,kt ,
0 5 k1 < k2 < · · · < kt < 2n − 1, be the vertices in the column indexed m − 1 that
are incident with jump edges of P . We insert two new columns on the right that will be
indexed m and m + 1. Detach the jump edge that is incident with um−1,k1 and make it
incident with um+1,k1 . Now take the path
um−1,k1um,k1um,k1+1 · · ·um,k2−1um+1,k2−1um+1,k2−2 · · ·um+1,k1
from um−1,k1 to um+1,k1 through the two new columns. If we do this for each jump edge,
we get a Hamilton path from u0,0 to um−1,j in HTG(m+ 2, 2n, s).
For the final special case, suppose we have a Hamilton path P from u0,0 to u0,j in
HTG(m, 2n, s) and we want a Hamilton path from u0,0 to u2,j in HTG(m+ 2, 2n, s). If
the terminal edge of P is a vertical edge, we add the flat edge u0,ju1,j to P and now use
the flat edges of P , together with the new flat edge, to insert two new columns between
the columns indexed 0 and 1. We make one small adjustment to the insertion procedure,
namely, we don’t include the new flat edge between u1,j and the vertex in the new column
to the left. Thus, upon reindexing the columns, we have a Hamilton path from u0,0 to u2,j
in HTG(m+ 2, 2n, s).
If the terminal edge of P is u1,ju0,j , the extension is more complicated. Because we
may assume that P is non-twisted, we know that the initial edge of P is either u0,0u0,1 or
u0,0u0,n−1. We insert two columns to the left of the column indexed 0 and index them α
and β from left to right. Let u0,k1 , u0,k2 , . . . , u0,kt , 0 < k1 < k2 · · · k2 < n − 1, be the
vertices in the column indexed 0 that are incident with jump edges in P . Insert the path
uα,0uα,1 · · ·uα,k1−1uβ,k1−1uβ,k1−2 · · ·uβ,0u0,0
B. Alspach et al.: Hamilton paths in Cayley graphs on generalized dihedral groups 39
into the new graph. For each of the other vertices u0,kr , detach the jump edge incident with
u0,kr and attach it to uα,kr , and insert a path from uα,kr to u0,kr similar to the path from
uα,0 to u0,0. After reindexing the columns we have a Hamilton path from u0,0 to u2,j in
HTG(m+ 2, 2n, s).
The above operations allow us to insert an even number of columns to the left and to
the right of a column containing the terminal vertex of a Hamilton path starting at u0,0.
Note that the insertion procedure used in the preceding proof, never introduces twisted
Hamilton paths, that is, if a Hamilton path is not twisted, then after making any of the
insertions the resulting Hamilton path is not twisted.
We now want to prove a theorem about honeycomb toroidal graphs that will be used
as a building block for the proof of the main result. However, before doing so we prove a
lemma that will simplify the exposition.
Definition 3.3. A path P in HTG(2, 2n, s) with terminal vertices u and v is said to be
vertically extendable when it satisfies the following two properties:
1. u0,j belongs to P if and only if u1,j belongs to P , and
2. for each maximal segment u0,i1 , u0,i1+1, . . . , u0,i1+k of vertices not belonging to P ,
exactly one vertex from {u0,i1−1, u0,i1+k+1} is incident with a flat edge of P and the
other vertex is incident with a jump edge, although the jump edge need not belong to
P .
Note that the definition implies that a given flat edge cannot arise as the flat edge for
two different maximal segments not belonging to P . This property is used in the proof of
the next lemma.
Lemma 3.4. If P is a vertically extendable path in HTG(2, 2n, s) with terminal vertices
u and v, then there is a Hamilton path in HTG(2, 2n, s) with terminal vertices u and v.
Proof. Let P be the path described in the hypotheses. If P already is a Hamilton path,
then there is nothing to prove. Otherwise, consider a maximal segment u0,i1 , u0,i1+1, . . . ,
u0,i1+k of vertices not belonging to P . Without loss of generality assume that
u0,i1+k+1u1,i1+k+1
is the flat edge belonging to P . Replace this flat edge (see Figure 2) with the path
u0,i1+k+1u0,i1+ku0,i1+k−1 . . . u0,i1u1,i1u1,i1+1 . . . u1,i1+k+1.
If the unique flat edge had been u0,i1−1u1,i1−1, we make the obvious modification.
We perform the above operation for each unique flat edge associated with the maximal
segments of vertices not belonging to P . We have a Hamilton path and the terminal vertices
have not been altered. This completes the proof.
In the subsequent material, when we apply Lemma 3.4 to go from a path P with ter-
minal vertices u and v to a Hamilton path with terminal vertices u and v, we shall say that
we have extended P to a Hamilton path by vertical extension. Note that any jump edges
appearing in P remain in the vertical extension to a Hamilton path.
40 Ars Math. Contemp. 3 (2010) 29–47
t t
t tt t
t t
t tt t
=⇒
i1 i1
i1 + k i1 + k
Figure 2: Typical vertical extension insertion.
t tt t
t t
t t
u0,0
u1,2
Figure 3: Typical Hamilton path when s = 0.
Theorem 3.5. The honeycomb toroidal graph HTG(m, 2n, s) is Hamilton-laceable when-
ever m is even.
Proof. Since the graph HTG(m, 2n, s) is bipartite and vertex-transitive, it suffices to find
a Hamilton path from u0,0 to any vertex ui,j with i + j odd. Because of Lemma 3.2, it
then suffices to prove the following two facts: (1) there is a Hamilton path from u0,0 to
u1,j , j even, in GHT(2, 2n, s) that has both flat edges and jump edges; and (2) there is a
non-twisted Hamilton path from u0,0 to u0,j , j odd, in GHT(2, 2n, s) that uses both flat
and jump edges.
We handle the case that s = 0 first. The path starting u0,0u0,2n−1u1,2n−1 and now
works down going back and forth between the two columns terminates at u1,0. For all
other vertices u1,j , j > 0 even, we start the path u0,0u1,0 and then work up going back and
forth between the two columns until we reach vertex u0,j−1. We then go straight up the
column indexed 0 to u0,2n−1, across to the other column and down to u1,j (see Figure 3).
For vertices u0,j , j odd and j 6= 2n − 1, in the column indexed 0, start working up going
back and forth between the two columns until reaching u1,j−1. Then go to the top, across to
u0,2n−1, and then down to u0,j . The latter construction does not work for u0,2n−1 because
the resulting Hamilton path is twisted.
For the special case u0,2n−1, start with u0,0u1,0u1,2n−1. Then continue down the col-
umn indexed 1 until reaching u1,1. Then take the edge to u0,1 followed by going up the
column indexed 0 until reaching u0,2n−1. The resulting Hamilton path from u0,0 to u0,2n−1
uses one flat edge, one jump edge, and is not twisted. We have obtained Hamilton paths
from u0,0 to all target vertices that use both flat and jump edges. None of the Hamilton
paths are twisted and this completes the case for s = 0.
Henceforth, assume s > 0. For i = 0, 1, . . . , n− 1, let Q(i) denote the
B. Alspach et al.: Hamilton paths in Cayley graphs on generalized dihedral groups 41
3-path
u0,2iu0,2i+1u1,2i+1u1,2i,
and R(i) denote the 3-path
u0,2iu0,2i−1u1,2i−1u1,2i.
The subgraph formed by the jump edges and the edges of Q(0), Q(1), . . . ,
Q(n − 1) is spanning and regular of valency 2. Furthermore, a vertical cyclic shift by
two is an automorphism of the subgraph. Thus, its components are cycles of the same
length and the number of them is d = gcd(n, s/2). Note that the jump edge u1,2iu0,2i+s
joins the terminal vertex of Q(i) to the initial vertex of Q(i+ (s/2)). Let C(i) denote the
cycle containing Q(i) for i = 0, 1, . . . , d − 1. The subgraph formed by the jump edges
and the edges of R(0), R(1), . . . , R(n − 1) behaves in the same way with d cycles for its
components as well. Let C ′(i) denote the cycle containing R(i) for i = 0, 1, . . . , d− 1.
Let u1,j be any vertex, with j even, from the column indexed by 1. Suppose u1,j lies
on C(k). Starting at u0,0, traverse the entire cycle C(0) and terminate at u0,1. Then add
the edge u0,1u0,2. Now traverse the cycle C(1) from u0,2 to u0,3. Then add the edge to
u0,4 in C(2). Continue in this way obtaining a path from u0,0 to u0,2k that uses all the
vertices of C(0) ∪ C(1) · · · ∪ C(k − 1). Now from u0,2k traverse C(k), starting with
edge u0,2ku0,2k+1, until reaching u1,j . The path we have constructed from u0,0 to u1,j is
easily seen to be vertically extendable. Thus, we obtain a Hamilton path P (u1,j) from u0,0
to u1,j by vertical extension.
With the exception of P (u1,0), each of the Hamilton paths just constructed has both
flat edges and jump edges. The Hamilton path P (u1,0) has no jump edges because it is the
vertical extension of Q(0). The vertex u1,0 must be treated individually.
If d = 1, that is, C(0) itself is a Hamilton cycle, then C ′(0) also is a Hamilton cycle.
Build a path as follows. Start the path with the four vertices u0,0u0,2n−1u1,2n−1u1,2n−2.
Now traverse the cycle C ′(0) starting with the edge from u1,2n−2 to u1,2n−3. Because
C ′(0) is a Hamilton cycle, as we traverse it in the indicated direction, when we reach the
vertex u1,0 along the edge from u0,s, all vertices are distinct so that we have a path from
u0,0 to u1,0 that uses both flat edges and jump edges. It is vertically extendable so that the
subcase of d = 1 is finished.
Build a path as follows when d > 1. Start the path with the vertices u0,0u0,2n−1u1,2n−1
u1,2n−2. From the vertex u1,2n−2 traverse the entire cycle C ′(d− 1) to the vertex u1,2n−3.
From the vertex u1,2n−3 take the edge to u1,2n−4. From this vertex we traverse the entire
cycle C ′(d− 2) to the vertex u1,2n−5. We continue in this way until the cycles C ′(d− 1),
C ′(d − 2),. . . ,C ′(1) have been traversed and we are at the vertex u1,2n−2d which lies on
C ′(0). We now traverse C ′(0) in the direction that allows us to reach u1,0 along the edge
u1,0u0,s. This path has both jump edges and flat edges. Vertical extension then gives us a
Hamilton path from u0,0 to u1,0 with flat edges and jump edges.
We now have Hamilton paths from u0,0 to every vertex of the form u1,j , j even, with
flat edges and jump edges. We now turn our attention to vertices of the form u0,j , j odd.
When d = 1, a Posa exchange for P (u1,k) on the edge u1,ku0,k+s produces a Hamilton
path from u0,0 to u0,k+s+1. All of these Hamilton paths have flat edges and jump edges.
None of them are twisted except the Hamilton path that terminates at u0,1. Thus, we need
to find a non-twisted Hamilton path from u0,0 to u0,1.
For this special case we use the 3-pathsR(0), R(1), . . . , R(n−1) to form the Hamilton
path from u0,0 to u1,2−s noting that u0,1 is the successor of u0,2. When we perform the
42 Ars Math. Contemp. 3 (2010) 29–47
Posa exchange on the edge u1,2−su0,2, we obtain a non-twisted Hamilton path from u0,0
to u0,1.
We now have found Hamilton paths of the desired type from u0,0 to all vertices of the
form u0,j , j odd, when d = 1. We proceed slightly differently for d > 1.
Assume d > 1. A Posa exchange for P (u1,j) on the edge u1,ju0,j+s produces a non-
twisted Hamilton path from u0,0 to u0,j+s−1 whenever u0,j+s is a vertex of C(k), where
k 6= 0 and u0,j+s 6= u0,2k. For the special cases of u0,2k−1, 0 < k 5 d − 1, build
the required Hamilton path as follows. Traverse all of C(0) from u0,0 to u0,1. If k = 1,
then u0,2k−1 = u0,1 and the latter path is vertically extendable to a non-twisted Hamilton
path from u0,0 to u0,1. If k > 1, continue building the path by adding the edge u0,1u0,2,
and then traversing the entire cycle C(1) until reaching the vertex u0,3. If k = 2, then
u0,2k−1 = u0,3 and we use vertical extension to get a non-twisted Hamilton path from u0,0
to u0,3. It is obvious how to continue this so that we obtain non-twisted Hamilton paths
from u0,0 to vertices of the form u0,2k−1, 0 < k 5 d− 1.
We are left with the requirement of finding appropriate Hamilton paths from u0,0 to
vertices of the form u0,j , where j is odd and u0,j+1 belongs to C(0). Traverse all of C ′(0)
from u0,0 to u0,2n−1. The vertical extension of this path is a non-twisted Hamilton path
from u0,0 to u0,2n−1 containing both flat edges and jump edges.
Let u0,j be any vertex of the form u0,j , where j is odd and u0,j+1 belongs to C(0),
distinct from u0,2n−1. Traverse C ′(0) starting at u0,0 along the edge u0,0u0,2n−1 until
reaching the vertex u1,j+1−s. The resulting path is vertically extendable to a Hamilton
path joining u0,0 and u1,j+1−s. Now perform a Posa exchange on the resulting Hamilton
path using the edge u1,j+1−su0,j+1. The result is a non-twisted Hamilton path from u0,0
to u0,j that has both flat edges and jump edges. This completes the proof.
4 Proof of main theorem
The proof of the main theorem is divided into three cases: S1 = ∅, |S1| = 1, and |S1| =
2. The preceding section contains a proof that honeycomb toroidal graphs with an even
number of columns are Hamilton-laceable. This forms the basis for the proof of Theorem
1.8 when S1 = ∅. The other two cases rely on the lemmas proved in Section 2. As a
reminder, let X = Cay(DH ;S) be a Cayley graph on a generalized dihedral group DH
such thatDH = 〈H, τ〉, |DH | ≡ 0(mod 4), Cay(DH ;S) is connected, and |S| = 3. Recall
that S1 = S ∩ H and S2 = S ∩ Hτ .
Case 1. Let S1 = ∅.
The most we can hope for is that X is Hamilton-laceable because it is bipartite. We
prove this case by induction on |S2| with the base for the induction being |S2| = 3, where
all three elements belong to Hτ . Every element of S is an involution and produces a 1-
factor in X . Let Ij denote the 1-factor in X generated by τj , j = 1, 2, 3. Let Fij denote
the 2-factor in X arising from Ii ∪ Ij . Note that Fij is composed of vertex-disjoint cycles
each of which has length 2|τiτj |.
Let C(1) and C(2) be two of the cycles comprising Fij . If a vertex of C(1) is adjacent
to a vertex of C(2) via an edge of Ik, where Ik is the other 1-factor, then because τiτjτk =
τkτjτi, it is easy to see that alternate vertices of C(1) are adjacent to alternate vertices of
C(2). Because X is connected, it is easy to see that X is a honeycomb toroidal graph
HTG(m, 2n, s) with the cycles of Fij being the vertical columns and the edges of Ik being
the flat edges and jump edges. Note that n = |τiτj | and m is the number of components of
B. Alspach et al.: Hamilton paths in Cayley graphs on generalized dihedral groups 43
Fij .
Thus, if F12 has an even number of components, X is Hamilton-laceable by Theorem
3.5. So we suppose that F12 is HTG(m, 2n, s), where m is odd and n = |τ1τ2|. Because
|DH | is a multiple of 4, we then must have that n is even.
Now consider the components of F13. If we start at a vertex of the first column in
HTG(m, 2n, s) and alternately travel by τ1 and τ3, when we return to the first column we
have travelled by s + m around the cycle in a cyclic fashion. In other words, we have
jumped by (s + m)/2 between edges of I1. Hence, the number of components of F13 is
gcd(n, (s + m)/2). Similarly, the number of components of F23 is gcd(n, (s − m)/2).
Because m is odd, (s + m)/2 and (s −m)/2 have opposite parity. Then n even implies
that one of F13 or F23 has an even number of components. The resulting honeycomb
toroidal graph has an even number of columns and Theorem 3.5 implies thatX is Hamilton-
laceable.
Therefore, we conclude that X is Hamilton-laceable when S consists of three involu-
tions belonging to Hτ . Hence, we assume |S| > 3.
If there is some s ∈ S such that Cay(DH ;S − s) is connected, then this subgraph
is Hamilton-laceable by induction. Hence, we may assume that S − s generates a proper
subgroup of DH for all s ∈ S. Consider X ′ = Cay(DH ;S − s) for a particular s ∈ S.
The Cayley graph X ′ is disconnected with components all isomorphic to Y = Cay(〈S −
s〉;S− s). If Y has order divisible by 4, then Y is Hamilton-laceable by induction. Let Y1,
Y2, . . . , Ym be the components of X with respective bipartitions (A1, B1), (A2, B2), . . . ,
(Am, Bm). Each part Ai and Bi, i = 1, 2, . . . ,m, is a coset of a subgroup of H . Hence,
by Lemma 2.2, we may assume that the subscripts have been chosen so that there is a
perfect matching joining vertices of Ai and vertices of Bi+1, for i = 1, 2, . . . ,m − 1, and
vertices of Am with vertices of B1. We then may apply Lemma 2.3 to conclude that X is
Hamilton-laceable.
From the preceding, we see that it suffices to show that for some s ∈ S the order
of the components of Cay(DH ;S − s) is a multiple of 4. Choose an arbitrary s1 ∈ S.
The components of Cay(DH ;S − s1) must have even order because each element of S
generates a 1-factor. If Cay(DH ;S − s1) has components whose order is not a multiple of
4, then there must be an even number of components. The edges generated by s1 join these
components in a cyclic fashion so that if we now consider S − s2, where s2 6= s1, then
each component of Cay(DH ;S − s2) intersects each component of Cay(DH ;S − s1) in
the same even number of vertices so that Cay(DH ;S − s2) has components whose order
is divisible by 4. This completes the proof of Case 1.
Case 2. Let |S1| = 1.
Let X1 be the subgraph induced by X on H . If X1 is connected, then X must be K4
which certainly is Hamilton-connected. Hence, we assume that X1 is not connected so that
h generates a non-trivial 1-factor in both X1 and X2. Note that h commutes with every
element in S2 because h(hiτ) = hihτ = hiτh−1 = (hiτ)h. This is a useful fact.
Another useful fact is the following, namely, we prove that X is bipartite if and only if
removing h from S disconnects the graph, that is, X ′ = Cay(DH ;S−h) is not connected.
Assume that X ′ is connected and let P be a path joining u to uh in X ′. The path P must
have even length because X ′ is bipartite and u and uh lie in the same part. Joining u to uh
gives an odd length cycle in X so that X is not bipartite. On the other hand, if X ′ is not
connected, then for each edge uv in a fixed component C ofX ′, there is an edge joining uh
to vh in X ′. This implies that all of the edges from C generated by h in X go to another
44 Ars Math. Contemp. 3 (2010) 29–47
single component ofX ′. Hence,X ′ has exactly two components each of which is bipartite.
It is easy to see that X too is bipartite.
LetX denote the quotient graph obtained by contracting each edge of the perfect match-
ing generated by h to a vertex. The graph X is a Cayley graph on a generalized dihedral
group. It has a Hamilton path by Lemma 2.9. Hence, in X there is a spanning subgraph
isomorphic to Pn2K2. Lemma 2.6 implies that there is a Hamilton path from a corner
vertex to any vertex at odd distance from it. Thus, if X is bipartite, there is a Hamilton
path from a corner vertex to every vertex in the other part of the bipartition. Because X is
vertex-transitive, this is true for all vertices and we conclude that X is Hamilton-laceable.
Because of the preceding paragraph, we may assume that X is not bipartite. If the
quotient graph X has order a multiple of 4, then it has a Hamilton cycle by Case 1. Thus,
the original graph X has a spanning subgraph satisfying the hypotheses of Lemma 2.4.
This lemma then implies that X is Hamilton-connected.
This leaves us with the subcase that X is not bipartite and the order of X is of the form
2t, where t is odd. This subcase takes more work.
We induct on the cardinality of S2. When |S2| = 2, the quotient graph X must be a
Hamilton cycle because X is connected. This implies that X has a spanning subgraph sat-
isfying the hypotheses of Lemma 2.4 which, in turn, implies thatX is Hamilton-connected.
Assume that |S2| = r > 2 and the result holds whenever 2 5 |S2| < r. Choose s ∈ S2
and consider the subgraph X ′ = Cay(DH ;S − s). If X ′ is connected and not bipartite,
then it is Hamilton-connected by induction.
Next assume that X ′ is connected but bipartite. From the argument above, we know
that deleting the edges generated by h disconnects X ′. Because h commutes with all the
elements of S2, the removal of the edges generated by h produces two components C1 and
C2. By Lemma 2.9, the subgraph C1 has a Hamilton path. Using the Hamilton path and
the edges generated by h, we get a spanning subgraph Y ′ of X ′ isomorphic to P2t2K2.
Label the vertices of Y ′ with ui,j , where 0 5 i < 2t, j = 0, 1, ui,0ui,1 are the edges
generated by h, and ui,j is adjacent to ui+1,j for i = 0, 1, . . . , 2t − 2. Lemma 2.6 tells us
there is a Hamilton path from u0,1 to any vertex whose distance from u0,1 in Y ′ is odd.
Because the graph X is not bipartite, the deletion of the edges generated by h does not
disconnect X . This implies that the edges generated by s join vertices of C1 to vertices
of C2. Therefore, if we take the subgraph Y ′ and add the edges generated by s from the
vertices u0,0 and u0,1, we have a 2-matching of the form M(0, k, 1), k odd (in the notation
of Lemma 2.8). Let Y ∗ be the graph obtained by augmenting Y ′ with the 2-matching
M(0, k, 1). The subgraph of Y ∗ from i = 0 up through i = k is Hamilton-connected by
Lemma 2.4. Using this fact and Lemma 2.6 it is easy to show there is a Hamilton path from
u0,1 to any vertex v. other than v = uk,0. Thus, for every vertex v ∈ X , v 6= u0,1, there
is a Hamilton path with terminal vertices u0,1 and v. Because X is vertex-transitive, X is
Hamilton-connected.
We now move to the subcase that X ′ is not connected. If the components of X ′ are
Hamilton-connected, then Lemma 2.5 implies that X is Hamilton-connected. Hence, we
assume the components of X ′ are bipartite. This subcase is similar to the immediately
preceding one. Because the components C0,C1, . . . ,Cr are bipartite, each may be written
as Ci = (Ai, Bi, Ci, Di), where h edges join Ai to Bi and Ci to Di, and elements of S2
generate edges joining Ai to Ci and Bi to Di. We may then assume the subscripts are
chosen so that edges generated by s join vertices of Ai to vertices of Ci+1, and vertices of
B. Alspach et al.: Hamilton paths in Cayley graphs on generalized dihedral groups 45
Bi to vertices of Di+1 for i = 0, 1, . . . , r − 1. Because X is not bipartite, we must have s
producing edges joining Ar to D0 and Br to C0.
We use Lemma 2.9 to get a path spanningAi ∪ Ci for i = 0, 1, . . . , r. BecauseAi ∪ Ci
is vertex-transitive, we may choose the beginning of the Hamilton path in Ai ∪ Ci to be
the vertex incident with the edge generated by s that is incident with the terminal vertex of
the Hamilton path in Ai+1 ∪ Ci+1. In this way we use edges generated by s to produce a
path spanning all the vertices of
A0 ∪A1 ∪ · ∪Ar ∪ C0 ∪ C1 ∪ · · · ∪ Cr.
We now use the edges generated by h to obtain a spanning subgraph Y of X isomorphic to
P2t2K2.
The subgraph Y is bipartite, but each time we use an edge generated by s, the parts
in the bipartition of a component are interchanged. Because each component has an even
number of h-edges and the total number of h-edges is 2t with t odd. There must be an
odd number of components. Hence, if we add the s-edges from the first edge of Y (from
component Cr) to some h-edge from component C0 we violate the bipartition, that is, we
have a matching M(0, k, 1) for some odd k. We then obtain that X is Hamilton-connected
as in the preceding subcase. This completes Case 2.
Case 3. Let |S1| = 2.
When X1 is connected, it either is an even length cycle spanning the vertices of H ,
when |S1| = 2, or it contains an even length cycle spanning the vertices of H because
of Theorem 1.7 when |S| > 2. Because X is connected, S2 6= ∅ so that there is a perfect
matchingM betweenX1 andX2. The spanning cycle ofX1, together with its obvious copy
in X2, then join the perfect matching edges M according to the hypotheses of Lemma 2.4.
The graph X is then Hamilton-connected or Hamilton-laceable, as required, by Lemma
2.4.
When X1 is not connected, let X be the quotient graph obtained by shrinking each
component of X1 and X2 to single vertices, where two vertices in X are adjacent if and
only if there is an edge between vertices in the two corresponding components.
The quotient graph X is a connected Cayley graph on a generalized dihedral group,
although its order may not be a multiple of 4. Nevertheless, the quotient graph X has a
Hamilton path by Lemma 2.9.
Each edge in X corresponds to a perfect matching between the corresponding cycles
in X by Lemma 2.2. Thus, the Hamilton path in X corresponds to a spanning subgraph
of X that is isomorphic to Pn2Cm. When m is odd, this spanning subgraph is Hamilton-
connected by Lemma 2.7. Thus, X also is Hamilton-connected.
When m is even, the spanning subgraph is Hamilton-laceable by the same lemma. If
X is bipartite, then it is Hamilton-laceable and we are done. If X is not bipartite, then we
have a little more work to do.
One reason that X may not be bipartite, is that the components of X1 and X2 are
not bipartite. Because m is even and the components of X1 and X2 are not bipartite, the
valency of the vertices in the components has to be at least 3. Theorem 1.7 then implies the
components are Hamilton-connected. It follows that X is Hamilton-connected by Lemma
2.5.
Finally, suppose the components are bipartite but X is not bipartite. Consider the span-
ning subgraph Pn2Cm. We have thatm is even andm > 2 because |S1| = 2. We have that
46 Ars Math. Contemp. 3 (2010) 29–47
n is even and n = 4 because each ofX1 andX2 is not connected and the two have the same
number of components. The spanning subgraph Pn2Cm uniquely determines a bipartition
of the vertices of X . Because the components themselves are bipartite, there are no edges
generated by elements of S1 that can violate the bipartition. Thus, there is at least one ele-
ment of S2 whose edges violate the bipartition. In other words, in the notation of Lemma
2.8, there is an m-matching M(i, k, d) whose edges violate the bipartition. This forces
both k and d to be odd. It then follows from Lemma 2.8 that X is Hamilton-connected.
This completes the proof of Theorem 1.8.
The following two corollaries are immediate consequences of the main theorem and we
specifically mention them here because hamiltonicity for Cayley graphs on dihedral groups
has been studied with some intensity.
Corollary 4.1. If X is a connected Cayley graph on the dihedral group Dn, n even, then
X has a Hamilton cycle.
Corollary 4.2. Every edge of a connected Cayley graph on a dihedral group Dn, n even,
lies in a Hamilton cycle.
References
[1] B. Alspach and C.C. Chen, On the hamiltonian laceability of brick products of even cycles,
Research Report No. 468, May 1991, Lee Kong Chian Centre for Mathematical Research.
[2] B. Alspach, C. C. Chen and K. McAvaney, On a class of Hamiltonian laceable 3-regular graphs,
Discrete Math. 151 (1996), 19–38.
[3] B. Alspach and M. Dean, Honeycomb toroidal graphs are Cayley graphs, Inform. Process. Let-
ters, to appear.
[4] B. Alspach and Y. Qin, Hamilton-connected Cayley graphs on Hamiltonian groups, Eu-
rop. J. Combin. 22 (2001), 777–787.
[5] B. Alspach and C. Zhang, Hamilton cycles in cubic Cayley graphs on dihedral groups, Ars
Combin. 28 (1989), 101–108.
[6] A. Altshuler, Hamiltonian circuits in some maps on the torus, Discrete Math. 1 (1972), 299–
314.
[7] C. C. Chen and N. Quimpo, On strongly Hamiltonian Abelian group graphs, in: K. L. Mca-
vaney (ed.), Combinatorial Mathematics VIII, Lecture Notes in Mathematics 884, Springer,
Berlin, 1981, 23–34.
[8] H. Cho and L. Hsu, Ring embedding in faulty honeycomb rectangular torus, Inform. Pro-
cess. Lett. 84 (2002), 277–284.
[9] H. Cho and L. Hsu, Generalized honeycomb torus, Inform. Process. Lett. 86 (2003), 185–190.
[10] C. Fan, D. R. Lick and J. Liu, Pseudo-Cartesian product and Hamiltonian decompositions of
Cayley graphs on Abelian groups, Discrete Math. 158 (1996), 49–62.
[11] D. Marušič and T. Pisanski, Symmetries of hexagonal molecular graphs on the torus, Croatica
Chem. Acta 73 (2000), 969–981.
[12] G. M. Megson, X. Liu and X. Yang, Fault-tolerant ring embedding in a honeycomb torus with
node failures, Parallel Process. Lett. 9 (1999), 551–561.
[13] G. M. Megson, X. Yang and X. Liu, Honeycomb tori are Hamiltonian, Inform. Process. Lett.
72 (1999), 99–103.
B. Alspach et al.: Hamilton paths in Cayley graphs on generalized dihedral groups 47
[14] B. Parhami, A unified formulation of honeycomb and diamond networks, IEEE Trans. Parallel
Distrib. Systems 12 (2001), 74–80.
[15] X. Yang, D. J. Evans, H. Lai and G. M. Megson, Generalized honeycomb torus is Hamiltonian,
Inform. Process. Lett. 92 (2004), 31–37.