IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 49 (2011), 1140
ISSN 2232-2094
ON CONNECTIVITY AND HAMILTONICITY OF DIRECT GRAPH BUNDLES
Irena Hrastnik Ladinek Janez Zerovnik
Ljubljana, March 8, 2011
On connectivity and hamiltonicity of direct
graph bundles *
oo	„
Irena Hrastnik Ladineka, Janez Zerovnikb'c
O
a FME, University of Maribor, Smetanova 17, Maribor 2000, Slovenia.
o
o
b FME, University of Ljubljana, Askerceva 6, Ljubljana 1000, Slovenia.
Institute of Mathematics, Physics and Mechanics, Jadranska 19, Ljubljana 1000, Slovenia.
-
Abstract
o
A necessary and sufficient condition for connectedness of direct graph bundles where the fibers are cycles is given. It is also proved that all connected direct graph bundles X = Cs xa Ct are Hamiltonian.
Key words: Hamiltonian graph, connected graph, direct graph product, direct
graph bundle, cyclic £-shift, reflection. -
1 Introduction
It is well-known that the Cartesian product of two Hamiltonian graphs is Hamiltonian, and therefore it is interesting to investigate conditions under which the product is Hamiltonian if at least one of the factors is not Hamiltonian. In 1982, Batagelj and Pisanski [1] proved that the Cartesian product of a tree T and a cycle Cn has a Hamiltonian cycle if and only if n> A(T), where
* This work was supported in part by the Slovenian research agency, grant Pl-0285-0101.
Email addresses: irena.hrastnik@uni-mb.si (Irena Hrastnik Ladinek), janez.zerovnik@imfm.uni-lj .si (Janez Zerovnik).
Preprint submitted to Elsevier
A (T) denotes the maximum vertex degree of T. They introduced the cyclic Hamiltonicity cH(G) of C as the smallest integer n for which the Cartesian product CnaG is Hamiltonian. More than twenty years later, Dimakopoulos, Palios and Paulakidas [2] proved that cH(G) < T>(G) < cH{G) + 1, as conjectured already in [1]. (Here T>(G) denotes the minimum of A(T) over all spanning trees T of G.) These results can be extended in a certain way to Cartesian graph bundles, see [7] and [6].
CSI
It is natural to ask whether similar theory may be developed for other graph products. In the case of direct product, the question of hamiltonicity seems to be much more complicated, because even the direct product of two cycles is not necessarily Hamiltonian ([5] gives a characterization which direct products of Hamiltonian graphs are Hamiltonian). For example, the direct product of two even cycles is not connected so it can not be Hamiltonian. Furthermore, the product of a tree (on at least 3 vertices) with any graph is not Hamiltonian, However, the direct graph bundle with even cycles as base and as fiber can be connected. When is it Hamiltonian?
0
In this paper, we study the connectivity and hamiltonicity of direct graph bundles. We give a complete list of necessary and sufficient conditions for connectedness of graph bundles where the fibers are cycles (Theorem 4.4). In special case when also the base graph is a cycle, a complete list of connected bundles can be written. More precisely, we prove:
1
Theorem 1.1 The direct graph bundle Cs xa Ct, with fiber Ct, and base Cs, CO	s.t > 3, is connected:
(1)	iftis odd, for any automorphism a G Aut(Ct).
(2)	ift is even, and s is odd if and only if a is identity, even cyclic £-shift or reflection with two fixed points p2.
(3)	ift is even, and s is even, if and only if a is odd cyclic £-shift, or reflection without fixed points po.
Otherwise, Cs xa Ct is not connected.
fc
Then we study hamiltonicity of direct graph bundles where both fibers and bases are cycles. We prove that all connected direct bundles of cycles over cycles are Hamiltonian:
.CD
Theorem 1.2 Let X = Cs xa Ct be a direct graph bundle with fibre Ct and base Cs. X is Hamiltonian if and only if X is connected.
The rest of the paper is organized as follows. In the next section we introduce terminology and notation, and recall some basic definitions including the definition of graph bundles. In Section 3 we consider a simple case, bundles over P2, for a later reference. In Section 4 we study the connectivity of direct bun-
dies: first a complete characterization of bundles of cycles over cycles is given, and then a necessary and sufficient condition for bundles over arbitrary base is proved. Hamiltonicity of direct graph bundles is discussed in Section 5. Finally, constructions of Hamiltonian cycles of direct bundles of cycles over cycles are given, first constructions for shifts (Section 6) and then for reflections (Section
7).
2 Terminology and notation
A finite, simple and undirected graph G = (V{G),E(G)) is given by a set of vertices V(G) and a set of edges E{G). As usual, the edges {i,j} E E(G) are shortly denoted by ij. Although here we are interested in undirected graphs, the order of the vertices will sometimes be important, for example when we will assign automorphisms to edges of the base graph. Is such case we assign two opposite arcs {(i, j), (j,i)} to edge {i, j}.
£
Two graphs G and H are called isomorphic, in symbols G ~ H, if there exists a bijection ip from V{G) onto V(H) that preserves adjacency and nonadja-cency. In other words, a mapping ip : V(G) —>■ v(H) is an isomorphism when: <p(i)(p(j) E E(H) if and only if ij E E(G). An isomorphism of a graph G onto itself is called an automorphism. The identity automorphism on G will be denoted by ida or shortly id.
CO
The cycle Cn on n vertices is defined by V(Cn) = {0,1,..., n — 1} and ij E E(Cn) if i = j±l mod n. Pn is the path on n > 1 distinct vertices 0,1,2,..., n— 1 with edges ij E E(Pn) if j = i + l,0 < i < n — 1. (Note that a subgraph isomorphic to the path graph is also called path.)
CO
An arbitrary connected graph G is said to be Hamiltonian if it contains a spanning cycle called a Hamiltonian cycle.
Let G and H be connected graphs. The direct product of graphs G and H is the graph G x H with vertex set V{G x H) = V(G) x V(H) and whose edges are all pairs (gi, hi)(g2, h2) with gig2 E E{G) and hih2 E E(H). Other names for the direct product are [4]: Kronecker product, categorical product, tensor product, cardinal product, relational product, conjunction, weak direct product or just product and even Cartesian product. The direct product of graphs is commutative and associative in a natural way. For more facts on the direct product of graphs and other graph products we refer to [4].
£
Let B and G be graphs and Aut(Gr) be the set of automorphisms of G. To any ordered pair of adjacent vertices u,v E V(B) we will assign an automorphism of G. Formally, let a : V(B) x V(B) ->• Aut(G). For brevity, we will write
A
o
a(u,v) = aUjV and assume that aVjU = cr~l for any u, v E V{B). Now we construct the graph X as follows. The vertex set of X is the Cartesian product of vertex sets, V(X) = V(B) x V(G). The edges of X are given by the rule: for any bi&2 G E{B) and any gig2 E E(G), the vertices (61,^1) and {b2, abub2(g2)) are adjacent in X. We call X a direct graph bundle with base B and fibre G and write X = B xCT G.
Clearly, if all ou<v are identity automorphisms, the graph bundle is isomorphic to the direct product X = Bx<TG = BxG. Furthermore, it is well-known that if the base graph is a tree, then the graph bundle is always isomorphic to a product, i.e. X = Tx°G~TxG for any graph G, any tree T and any assignment of automorphisms a [8].
A graph bundle over a cycle can always be constructed in a way that all but at most one automorphism are identities. Fixing V(Cn) = {0,1, 2,..., n — 1} we denote crn_ = cn, <?i-i,i = id for i = 1, 2,..., n — 1, and Cnxa G ~ Cn xCT G.
3 Bundles over K2
Automorphisms of a cycle are of two types. A cyclic shift of the cycle by £ elements or briefly cyclic £-shift, 0 < I < n, maps Ui to ui+i (index modulo n). As a special case we have the identity (£ = 0). Other automorphisms of cycles are reflections. If Cn is a cycle on odd number of vertices, then all the reflections have exactly one fixed point. If the number n is even, then we have reflections without fixed points and reflections with two fixed points.
More formally, we define:
CO	. .
•	cyclic ^-shift, a^, defined as = (i + £) modn for i = 0,1,..., n — 1.
•	reflection with no fixed points p0, defined as p0(i) = n — i — 1 for i = 0,1,..., n — 1. (For n even there is no fixed points.)
•	reflection with one fixed point pi defined as pi(i) = n — i — 1 for i = 0,1,... ,n — 1. (For n odd, there is exactly one fixed point,	=
n-V"l = ¥•)
•	reflection with two fixed points p2 defined as ^2(0) = 0 and p2(i) = n — i for i = 1, 2,..., n — 1. (For n even, there is the second fixed point p2(f)=n-f = f.)
CO
We first show that the graph bundle P2 xa Ct is either isomorphic to one or to two cycles. (See also Figures 1 and 2.)
Lemma 3.1 The direct graph bundle P2 xa Ct for odd t is isomorphic to the cycle C2t for every automorphism a of Ct- If t is even, then for every
automorphism a of Ct the graph bundle P2xaCt has two connected components that are isomorphic to Ct.
,fi
o u ti
Proof: First note that each vertex of P2xaCt is of degree two, hence the graph is a union of cycles. Now consider vertex (0, i). Observe that the vertices at distance two are (0, (i + 2) modi) and (0, (i — 2) modi). (Using the fact that (0, i) and (0, (i + 2)modt) have a common neighbor (1 ,a(i + 1)) and (0, i) and (0, (i — 2) modi) have a common neighbor (1, a{i — 1)).) Hence if t is even the vertices (0, i) for even i are on one cycle, and consequently it must be of length t. Similarly, vertices (0, i) for odd i are on the other cycle of the same length. If t is odd then all vertices (0, i) are on the same cycle. □
o
Let us emphasize that the lemma applies to the product (case a = id). Remark 3.2 P2x Ct — C2t if t is odd and P2 x Ct — 2Ct ift is even.
0
o
1
00
£ CO CO
For a later reference let us write explicitly the vertex sets that induce the two cycles of P2 xa Ct for even t. Denote the subsets of odd and even vertices of Ct by Wi = {1,3,..., 2r^l - 1} and W0 = {0,2,4,..., 2L^J}, respectively. Hence V(Ct) = W0 U and recall that V(P2) = {0,1}. From the proof of Lemma 3.1 the next two lemmas directly follow.
Lemma 3.3 Let t be even and a be identity, an even shift or reflection p2. Then V{Ci0)) = Z0 = ({0} x W0) U ({1} x Wx) and V{C\1]) = Z1 = ({0} x W\) U ({1} x Wo).
Lemma 3.4 Let t be even and a be an odd shift or reflection po- Then V(C^) = {0,1} x Wq and V(Ct(1)) = {0,1} x Wi.
CO CD
Jh
CD CO
4 3 2 1 0
4 3 2 1 0
4 3 2 1 0
u
a
CD U
a)
b)
c)
Fig. 1. The direct graph bundles P2 xa C5: a)a = id, b)a = ai and c)a — p\
0 1 0 1 0 1
a)	b)	c)
O
Fig. 2. The direct graph bundles P2xa a)a = id, b)a = p2 and c)a = po
i—l
4 Connectivity of direct graph bundles
O
The fact that the direct product G x H of connected and bipartite factors G and H has exactly two components was first proved by Weichsel [9]. Hence if G and H are bipartite, then Gx H can not be Hamiltonian. In particular, the direct product Cs x Ct, where Cs and Ct are even cycles, is not connected and hence not Hamiltonian.
Below we give necessary and sufficient conditions for connectivity of a direct graph bundle CsxaCt and for graph bundles with fibre Ct over arbitrary base graph B. The case when t is odd is easier and is considered first.
Lemma 4.1 Let Ct be a cycle on t vertices, where t is odd. Then B xa Ct is
CO
connected for every connected base qraph B.
CO
Proof: Follows directly from Lemma 3.1. □
As B = Cs is just a special case of interest, we can write
Corollary 4.2 Let t be odd. The direct graph bundle Cs xa Ct is connected for every automorphism a e Aut(Ct).
m
We now consider the graph bundles with fiber Ct for even t and this time we start with the case when the base graph is a cycle. We first observe a subgraph ofCsxa Ct in which the edges corresponding to the only (possibly) nontrivial automorphism are missing. As the subgraph Ps x Ct is not connected, we have to look at the missing edges to see whether Cs xa Ct is connected.
Let us denote V(PS) = V{CS) = V0UV1 where V0 = {0,2,4,..., 2[^J} and V\ = {1,3,...,	— 1} are the sets of even and odd vertices. Similarly,
write V{Ct) = Wq U Wx, a union of odd and even vertices. Furthermore, write
00
,fi
o u ti
o
0 o
1
CO ^
CO CO
CO CD
$H
CD CO
Zo = (Vo x Wo) U (Vi x Wi) Zx = (V0 x Wx) U (Vi x W0).
Lemma 4.3 If t is even, then the direct product Ps x Ct has two connected components, the first induced by the vertices of ZQ and the second on the vertices from Z\.
The proof is straightforward and therefore ommited.
For s odd, the graph Cs xa Ct will be connected exactly when there is an edge connecting the set {s — 1} x Wq with {0} x Wx (or there is an edge connecting the set {s — 1} x Wx with {0} x W0). This is true exactly when the automorphism a is the identity, even cyclic shift or reflection with two fixed points (see Lemma 3.3). On the other hand, when a is odd cyclic shift or reflection without fixed points, there is no such edge by Lemma 3.4.
By analogous reasoning as above CsxaCt for even s will be connected exactly when there is an edge connecting the set {s — 1} x Wo with {0} x Wq, or {s — 1} x Wx with {0} x Wx- This is when the authomorphism a is odd cyclic ^-shift or reflection without fixed points (recall Lemma 3.4). On the other hand, if the automorphism a is either identity, even cyclic ^-shift or reflection with two fixed points, there is no such edge (by Lemma 3.3), and therefore Cs xa Ct is not connected in these cases.
The observations are summarized in Theorem 1.1 and in Table 1. Table 1
Connected direct graph bundles Cs x" Ct
t odd	for any automorphism a of Ct	
t even	s odd	List 1, Cx-
		a = id
		a — at, I is even
		OL = P2
	s even	List 2, a — at, I is odd a = po
U
a
CD U
Recall that all graph bundles with connected base B and fibre Ct for odd t are connected. We conclude the section stating a necessary and sufficient
condition for connectedness of a graph bundle with connected base B and fibre Ct for even t.
O
Theorem 4.4 Let X be a direct graph bundle with fiber Ct. If Ct is an odd cycle, then X is connected. If Ct is an even cycle, then X is connected if and only if there is a cycle C = v\v2 ... v^ in B such that either
00
•	|V(C)| = k is odd and a = vVkjV1 o aVs_ljVg o • • • o aV2V3 o aviv2 is an automorphism from L\, or
•	|V(C)| = k is even and a = crVk!Vl o aVs_ljVs o • • • o aV2V3 o aVlV2 is an automorphism from £2 •
Proof: (sketch) If the fibre Ct is an odd cycle, X is clearly connected.
Let Ct be an even cycle. (1) First assume that X is connected. Let T be an arbitrary spanning tree of B. Then the subgraph spanned by edges of T, T xCT Ct has two connected components, and V2. There must be an edge e = (bi,gi)(b2,g2) in X that connects two vertices from different components V\ and V2. Let p(e) = b\b2 be the projection of this edge to B. There is a unique path P that connects b\ and b2 in T. The subgraph of X over the cycle C = PUp(e), C
xCT Ct, is connected, hence the automoprhism on the edges of C must be as claimed.
o
(2) Now assume there is a cycle C in X that fulfills the conditions given in the theorem. Then C xCT Ct is connected which directly implies that X is connected. □
5 Hamiltonicity of the direct graph bundles
CO
Obviously, a Hamiltonian graph is connected, so from now on we will only be interested in the direct graph bundles that are connected graphs. Among connected graphs, we can easily exclude the direct graph bundles over trees. One can easily prove that the direct product of a tree T ^ P2 and an arbitrary graph G is not Hamiltonian. The statement also holds for graph bundles:
Lemma 5.1 Let T P2 and G an arbitrary connected graph. Then the direct graph bundle T xCT G is not Hamiltonian.
fi
Proof: Let G be a graph on n vertices. Suppose for contradiction that the bundle T xCT G is Hamiltonian and let C be a Hamiltonian cycle. Projection of C to the base graph T spans all vertices of T. Let us walk along C and count how many times each vertex of T is visited and how many times edges will be traversed. Let fibea vertex of degree one. As T P2, u has a neighbor, say v, with degree more than one. The vertex u has to be visited exactly n
U
CU
times, hence the edge uv is traversed n times in each direction. As v has other neighbors, there is an edge vw that is used at least once, but then the vertex v was visited more than n times, or, equivalently, at least one of the vertices
(v,*) has been visited twice in C. Contradiction. □
V > J
Therefore we will start with direct graph bundles of cycles over cycles. In the next two sections several constructions of Hamiltonian cycles will be given which will prove that all connected graph bundles X = Cs xa Ct with fibre Ct and base Cs are Hamiltonian. Formally, the constructions that will be given in the last two sections will imply
Theorem 1.2. Let X = Cs xa Ct be a direct graph bundle with fibre Ct and base Cs. X is Hamiltonian if and only if X is connected.
o
We postpone the proof of this theorem to the last two sections.
A
O
o
This theorem, together with the Theorem 1.1, implies
Theorem 5.2 Let B and F be Hamiltonian graphs, with t = | V(F)| odd. Then any direct graph bundle X with fiber F and base graph B is Hamiltonian.
Proof: Consider the subgraph Cb xa Cf of X that has vertex set V(Cb) x V{CF) = V{B) x V{F) and edges defined by the rule: for any b{b2 G E(CB) and any gig2 G E{Cp), the vertices (&i,<7i) and (b2, Cfei^G^)) are adjacent. Clearly, Cb xaCp is Hamiltonian by Theorem 1.2 and because it is a spanning subgraph of X, X is Hamiltonian. □
For t = 1^(^)1 even we are only able to state sufficient conditions for Hamiltonicity.
CO
Theorem 5.3 Let B and F be Hamiltonian graphs, with t = 1^(^)1 even. Then we have:
•	Let s = \V(B)\ be odd. A direct graph bundle X with fiber F and base graph B is Hamiltonian if there is a Hamiltonian cycle Cb = v\v2 ■ ■ - vs in B such that a = crVs!Vl o aVs_1>Vs o • • • o aV2V3 o aVlV2 is an automorphism from L\.
•	Let s =	be even. A direct graph bundle X with fiber F and base graph B is Hamiltonian if there is a Hamiltonian cycle Cb = v\v2 .. .vs in B such that a = aVs V1 o av _1 Vs o • • • o aV2V3 o aviv2 is an automorphism from
u	' '
CD
Proof: (sketch) Consider the spanning subgraph Cb xct Cp of X as in the proof of Theorem 5.2. Observe that Cb xa Cf — Cb xa Cf where a = crVa!V1 o ffvs-i,vs o---o crV2V3 o crviv2 and all other automorphisms are identities. If s is even, then by Theorem 1.1 Cb xa Cf is Hamiltonian exactly when a is odd cyclic ^-shift or reflection without fixed points, as claimed.
The same Theorem implies the condition for odd t. □
The next two sections provide proofs (constructions) that together imply correctness of Theorem 4.4. We start with shifts and first give a construction that provides a union of cycles which cover Cs xa Ct with p cycles. When p > 1 another construction will be used to combine the p cycles into one Hamiltonian cycle. Reflections will be considered in the last section: four different constructions will cover all possible cases.
A
o u
o
CO
6 Hamiltonicity of the direct graph bundles - cyclic shifts
Construction 1. Let X be the subgraph of Cs xCT< Ct in which only edges {i,j)(i + 1, {j + 1) modi), i = 0,1,..., s - 2, j = 0,1,... t - 1 and (s - 1 ,j) (0, (j + 1 + I) mod t), j = 0,1,... t - 1 are present. □
Informally, one can also say that in X, reading from left to right, only edges directed "up" are taken from X.
Obviously, vertices of X are of degree two, so X is a union of cycles (see Figure
4, a) and b)). Due to obvious symmetry, we have
Lemma 6.1 X is isomorphic to a union ofp cycles of length Moreover p is odd number and the i-th cycle meets the first fibre in vertices (0, (i+p) mod t).
00
If p = 1 then X gives a Hamiltonian cycle of X, but this is of course not always the case. (Examples with p = 1 and p = 3 are given on Figure 4.a) and b).) Now we will show how one can always combine the cycles into one by replacing only a few edges.
Construction 2. Let X be a subgraph of X that is a union of cycles. Delete edges (1, i)(2, i + 1) and (0, i + 1)(1, i + 2) and replace them with edges (0, i + 1)(1, i) and (1, i + 2)(2, i + 1) for i = 0,1, 2,.. .p - 2 to obtain X. □
Assuming that the edges of X between fibres 0,1, and 2 are as given by Construction 1, (i.e. all edges go "up") we have the situation on Figure 3. The result of Construction 2 on the graph from Figure 4.b) is given on Figure 4.c).
.CD
By Lemma 6.1, the edges (1,i)(2,i + 1) and (0,i + 1)(1, i + 2) are on the i-th and i + 2-th cycle. The replacement thus combines the two cycles into a larger one. Note that the edges involved in Construction 2 for different i are disjoint
and that p is odd. Therefore -
Lemma 6.2 Let X be obtained by Construction 1 and assume it has p > 1 cycles. Then X, the result of Construction 2 (replacing p — 1 pairs of edges)
gives a Hamiltonian cycle.
,fi
o u ti
o
0 o
1
CO
£ CO CO
0 1 2
Fig. 3. Construction 2. We connect cycles p parallel into one (Hamiltonian) cycle.
5
4
3
2
1
0
1 b)
c)
Fig. 4. a) X is a Hamiltonian cycle in C4 xCTl C5, b)X in C3 x Cq has 3 cycles, c) Hamiltonian cycle in C3 x Cq
7 Hamiltonicity of the direct graph bundles - reflections
m
CD
Jh
CD
m
u
a
CD U
In this section we give constructions of Hamiltonian cycles for connected graph bundles of cycles over cycles where the nontrivial automorphism is a reflection. The four propositions treat cases according to parity of the lengths of cycles, s and t.
Theorem 7.1 Let Cs, Ct be two cycles, where s,t> 3 and s is odd andt even. Let a = P2 be reflection with two fixed points. Then Cs xa Ct is Hamiltonian.
Proof: The Hamiltonian cycle is constructed as follows, t disjoint paths of length s — 1 from (0, j) to (s — l,j), j = 0,1,..., t — 1 are formed by taking (for example) edges (i,j)(i + 1, (j + 1) modi)) for even i and edges (i,j)(i + 1, (j — 1)modt) for odd i (and j = 0,l,...,t — 1). The edges between fibres
s — 1 and 0 are chosen from (0, i)(l,p2(i + 1 )),i G W0, and from Ct
(i).
,fi
o u ti
o
0 o
1
00 ^
CO CO
m
CD
$H
CD
m
u
a
CD U
(0, i)(l,p2(i —1)),« G Wl, or, equivalently, from C^: (0,i)(l, p2(i) — l),i G Wo, and from Cf}: (0, z)(l, p2{i) + l),i G Wi
(recall the partition of edges of P2 xP2 Ct from Lemma 3.3), see Figure 5.)
The claim that these edges form a Hamiltonian cycle is easy to check, for example by observing that the edges (0, z)(l, p2{i) — 1), i G Wo, and (0, i)(l, p2{i) + 1), i G W\ give rise to a permutation of the set {0,1,..., t — 1} with one cycle. We omit the details. □ 5
4
3 2 1 0
0
Fig. 5. The direct graph bundle C3 x^2 C6 (left), and the cycles Cf} C,
(0)
6
Theorem 7.2 Let Cs,Ct be two cycles, where s,t > 3 and both s and t are even. Let a = po be reflection without fixed points. Then Cs xa Ct is Hamilto-
nian.
Proof: The subgraph induced on two consecutive fibres i and i + 1 (for i = 0,1,..., s — 2) has two connected components (the first on the vertices from Z0 and the second on the vertices from Zi) that are isomorphic to Ct. One of this cycles contains the edge (i, |)((i + 1) mods, | — 1), the other the edge (z,| - 1)((« + 1) mods, |).
Deleting edges (i, |)((« + 1) mods, | — 1) and (i, | — 1)((« + 1) mods, |) thus gives two disjoint paths that span all vertices (and all edges except the two deleted) of fibres i and i + 1.
Furthermore, the subgraph induced on fibres s — 1 and 0 has two connected components that are isomorphic Ct, by Lemma 3.1. The first is induced by the vertices of {s — 1,0} x W0, the second by the vertices of {s — 1,0} x Wi, by Lemma 3.4. Two disjoint paths that span all vertices (and all edges but two) of fibres s — 1 and 0 can be constructed by deleting the edges (s — 1, |)(0, |) and (s - 1, | - 1)(0, § - 1) (because p0(\ - 1) = § and p0(§) = § - 1).
A Hamiltonian cycle on Cs xa Ct is constructed as follows. On each of the pairs of fibres: 1 and 2, 3 and 4,..., s — 3 and s — 2 we take the two spanning
paths. Add the edges ((i + 1) mods, | — l)((i + 2) mods, |) and the edges ((i + 1) mod s, §)((« + 2) mod s, § - 1).
,fi
o u ti
o
0 o
1
CO ^
CO CO
Observation that the edges connect vertices from Z0 with vertices from Z0 (and vertices from Z1 with vertices from Zi) for i = 1,3,..., s — 3 and that the edges between fibres s — 1 and 0 connect Zq to Z\ and Z\ to Zq implies that a Hamiltonian cycle is constructed (see Figure 6). □
4
3 2 1
1 2 3 4 5 0 Fig. 6. The direct graph bundle C4 x« C6
Theorem 7.3 Let Cs, Ct be two cycles, where s, t > 3 and s is even andt odd. Let a = pi be reflection with one fixed point. Then Cs xa Ct is Hamiltonian.
Proof: Note that the edges between two consecutive fibres i and i + 1 (for i = 0,1,..., s — 2) form a cycle of length 21, because the subgraph induced on two consecutive fibres is isomorphic to x Ct. Also the subgraph induced on fibres s — 1 and 0 is isomorphic to P2 xpi Ct — C2t, by Lemma 3.1.
Each of these subgraphs contains the two edges (i, | )((i + 1) mods, | + 1) and (i, \ + 1)((« + 1) mods, f ).
m
CD
Jh
CD
m
Deleting edge (i, | )((z + 1) mods, vertices (and all edges except the de'
+ 1) thus gives a path that spans all eted) of fibres i and i + 1.
Now we can construct a Hamiltonian cycle on CsxaCt by taking the spanning paths on pairs of fibres 1 and 2, 3 and 4, .... s — 2 and s — 1 and 0, and connecting them with edges (i, | + l)(i + 1, | ), i = 0,2,4,..., s — 2 (see Figure 7.) □
U
a
CD U
Theorem 7.4 Let Cs,Ct be two cycles, where s, t > 3 and both s and t are odd. Let a = pi be reflection with one fixed point. Then Cs xa Ct is Hamiltonian.
1 2 3 4 5 0
O
Fig. 7. The direct graph bundle C6 xpi C5
Proof: Consider the following subset of edges (all additions in the second coordinate are modulo t):
(a)	{i,j)(i + l,j + 1) for i = 0,1,3,5,..., s - 2 and j = 0,1,..., t - 1,
(b)	(i,j)(i + l,j — 1) for i = 2,4,6,..., s — 3 and j = 0,l,...,t — 1, and
(c)	(s - U)(0,pi0" - 1)) for j = 0,1,... ,t - 1.
Observe that edges from (a) and (b) form t parallel paths that join (0,j) with (s — l,j + 2). As pi(j — 1) = t — (j — 1) — 1 = t — j, the edges defined in (c) can be written simpler as (s — 1, j)(0, t — j).
Clearly, the edges meet each vertex exactly twice, so they form a union of cycles. More precisely, we have one (short) cycle
CO
{s - 1,1) -)■ (0, t - 1) = (0, -1) ---->{s- 1,1)
and L§J longer cycles, namely for j = 2,3,..., |_§J, [|1
(s-l,j) (0,t-j)	(s-l,t-j+2) (0,t-(t-j+2) = (0,i-2) ^
HH
----y(s-lj).
Note that by construction each of the [|] cycles, for j = 1,2,..., f|"|, includes a path (0,j — 2) —> (1 ,j — 1) —> (2,j). Hence we can use the same idea as before (Construction 2 in Section 6) to obtain a Hamiltonian cycle from the |"H "parallel" cycles. □
^	A	n • •	•
An example is given m Figure 8.
m
References
[1] V. Batagelj, T. Pisanski, Hamiltonian cycles in the cartesian product of a tree and a cycle, Discrete Mathematics 38, 1982, 311 - 312.
o

CO CD
$H
CD CO
$H
a
CD U
0	12	3 4
Fig. 8. The direct graph bundle C5 C5
[2]	V. V. Dimakopoulos, L. Palios, A. S. Poulakidas, On the hamiltonicity of the cartesian product, Information Processing Letters 96, 2005, 49 - 53.
O
[3]	R. H. Hammack, Proof of a conjecture concerning the direct product of bipartite graphs, European Journal of Combinatorics 30, 2009, 1114 - 1118.
[4]	W. Imrich, S. Klavzar, Product Graphs, Structure and Recognition, John Wiley & Sons, New York, 2000.
C^
[5]	S. Gravier, Hamiltonicity of the cross product of two Hamiltonian graphs, Discrete Mathematics 170 (1997) 253-257.
[6]	I. Hrastnik Ladinek, J. Zerovnik, Cyclic Bundle Hamiltonicity, submitted.
[7] T. Pisanski, J. Zerovnik, Hamilton cycles in graph bundles over a cycle with tree as a fibre, Discrete Mathematics 309 (2009) 5432 - 5436.
CO
[8] T. Pisanski, J. Vrabec, Graph bundles, Prep. Ser. Dep. Math. 20, Ljubljana, 1982, 213 - 298.
[9] P. Weichsel, The Kronecker product of graphs, Proceedings of the American Mathematical Society 13, 1962, 47 - 52.