IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1139 ISSN 2232-2094 CYCLIC BUNDLE HAMILTONICITY Irena Hrastnik Ladinek Janez Zerovnik Ljubljana, March 7, 2011 CYCLIC BUNDLE HAMILTONICITY IRENA HRASTNIK LADINEK*, JANEZ ZEROVNIK** Abstract. Cyclic bundle Hamiltonicity cbH(G) of a graph G is the minimal n for which there is an automorphism a of G such that the graph bundle Cn^aG is Hamiltonian. We define V(GCK)min, an invariant that is related to the maximal vertex degree of spanning trees suitably involving the symmetries of G and prove cbH(G) < V(Ga)min < cbH(G) + 1 for any non-trivial connected graph G. 1. Introduction 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 A (T) denotes the maximum valence (or vertex degree) of T. They introduced the cyclic Hamiltonicity cH(G) of G as the smallest integer n for which the Cartesian product CnDG is Hamiltonian. More than twenty years later, Dimakopoulos, Palios and 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 graph bundles. Recently, Pisanski and Zerovnik [3] proved that the graph bundle Cn\JaT has a Hamiltonian cycle if over all and only if n > /i(T, a), where /i(T, a) is the maximum value of vertices v £ V(T) and o(v,a) denotes the number of elements in the orbit of v under the automorphism a while d(v, a) is the degree of the vertex corresponding to the orbit of v in the tree T/a. In this note, we show that the results for general graphs can naturally be generalized from Cartesian graph products to Cartesian graph bundles. As an analog of the cyclic Hamiltonicity cH(G) we define cyclic bundle Hamiltonicity cbH(G) of the graph G as the minimal n such that there exists a £ Aut(G) and CnDaG has a Hamiltonian cycle. We prove that d(v,a) o(v,a) cbH(G) < V(Ga)min < cbH(G) + 1 where ^ ^ V(Ga) = min |/z(Ta) | Ta is a spanning tree of j and (i) h(Ta) = max j d(w) o(w) W £ V(Ta) j where d(w) denotes the degree of the vertex w in Ta and d{w) is the number of elements in the orbit of the vertex w in Ta. 2000 Mathematics Subject Classification. Primary 05C45. Key words and phrases. Cartesian product, Cartesian graph bundle, Hamiltonian graph. This work was supported in part by the Slovenian research agency, grant Pl-0294-0101. As the result given in this paper directly generalizes the result of [3] that is valid for trees, it is natural to ask whether a brief argument is sufficient for the conclusion. On one hand, a Hamiltonian cycle of Cn\I\aT is clearly also a Hamiltonian cycle of Cn\I\aG for any spanning tree T of G, and similarly, a Hamiltonian cycle of Cn\I\aTa is also a Hamiltonian cycle of Cn\I\aGa. However, on the other hand, taking a spanning tree T of G, the sets of automorphisms of G and of T are in general different, hence direct application of theorem for trees is not straightforward. After a section with basic terminology and notation, a detailed proof is given in Section 3, and the result is illustrated with several examples. 2. Terminology and notation Here we will study hamiltonicity of a graph bundle Cn\JaG. An arbitrary connected graph G is said to be Hamiltonian if it contains a spanning cycle called a Hamiltonian cycle. The Cartesian product of graphs G and H is the graph G\I\H with vertex set ^ ^ GUH anV ^ ()>(#>) (d , ) j GUH.7 Let B and G be graphs and Aut(G) be the set of automorphisms of G. For any pair of adjacent vertices u, v G V(B) we will assign an automorphism of G to the Now we construct the graph X as follows. The vertex set of X is V(X) = and We call X = BUaG Cartesian graph bundle with base B and fibre G. Other standard graph products [4] can be generalized to graph bundles. Graph bundles were first studied in [6], and received considerable interest in the literature, see, for example [5, 7, 8, 9, 10, 11] and the references there. Clearly, if all au^v are identity automorphisms, graph bundle is the Cartesian product X = B\Z\aG = BUG. Furthermore, it is well-known [6] that if the base graph is a tree, then the graph bundle is isomorphic to the Cartesian product, automorphisms a. A graph bundle over a cycle can always be constructed in a way that all but There are two interesting cases where the construction above may not result in a simple graph. For n = 2, C^J^G has double edges whenever a fixes a vertex. For n = 1, CiOaG has a loop whenever a fixes a vertex and has double edges whenever vertices v and a(v) are adjacent in G. However, when interested in Hamiltonian properties, we can consider C^J^G and CilZPG as simple graphs by ignoring loops and multiple edges because a Hamiltonian cycle traverses each multiple edge at most once and never uses a loop. Let G be an arbitrary connected graph. Let a £ Aut G be an arbitrary automorphism of G. It partitions the vertex set V(G) into disjoint orbits. For a given vertex v £ V(G) let 0(y,a) denote such an orbit whose size is denoted by o(v, a). To simplify the notation, let Ga denote the quotient graph obtained from the graph G by vertex identification of each vertex orbit 0(v,a) and with two orbits 0(u,a) and 0(v, a) being adjacent in Ga if and only if there are two representatives u £ 0(u, a) and v £ 0(v,a) that are adjacent in G. By Ta we will denote a spanning tree of the quotient graph Ga. 3. Cyclic bundle Hamiltonicity Cyclic Hamiltonicity cH(G) of the graph G is the minimal n for which CnDG is Hamiltonian, where Cn is the cycle on n vertices [1]. As an analog we define here the cyclic bundle Hamiltonicity cbH(G) of the graph G as the minimal n for which there is an automorphism a £ Aut(G) such that CnDaG is Hamiltonian. If G is Hamiltonian, then cbH(G) = 1. In this case, Ci\3aG is Hamiltonian for every automorphism a of G. But the converse is not true. We may have cbH(G) = 1, yet G is not necessarily Hamiltonian. In Figure 1, G is not Hamiltonian CilZPG is drawn with thick lines. Figure 2 shows an example of Hamiltonian cycle Figure 1. a)The graph G, b)The graph bundle CiEPG where a = (1,2)(3,4) Let G be an arbitrary connected graph with the maximum degree A(G) > 2 and a an arbitrary automorphism of G. Let Ta be a spanning tree of the quotient graph denote the number of elements in the orbit of the vertex w in X^. Define h(Ta) = max < d(w) o(w) W £ V(Ta) and V(Ga) = min j/i(Ta) | Ta is a spanning tree of . In the sequel we will assume that A(G) > 2. Among connected graphs this excludes only P^ the path with one edge, and the graph with one vertex P\. These two cases are easy and will be treated separately. First we prove a technical lemma. Lemma 3.1. Let a £ Aut(G) and Ta be a spanning tree of the quotient graph Ga. are adjacent in Ta, let be the set of edges between the elements of the two orbits. There is a subset such that: • if w,x are adjacent in Ta then F C\ E(w,x) ^ 0, each Wj meets at most d(w) o(w) edges of F. Furthermore, there is a proper edge coloring of the subgraph induced on F with at Proof First we will build a set of subforests of Ta as follows. Start with To = Ta. Take a maximal subforest F\ of Ta such that the degree of a vertex w £ V(Fi) in F^ is d{w) o(w) (This can be done for example using a breadth first search of the o(w) for every vertex graph choosing the first edges met.) Note that when d(w) < If F\ ^ To then continue taking T\ = To — F\. Let F2 be a maximal subforest of Ti (constructed as above) such that the degree of a vertex w £ V(F2) in F2 is at most "2 If d(w) o(w) < dT±(w), then dp2{w) = 2 o(w) . If o(w Construct in this way further subforests Fi until Ti = 0. Observe that, by construction UFi = Ta. d(w) o(w) > dT±(w), then Recall that at each step (except at the least perhaps) the degree of the vertex w £ Ti is decreased by Hence, because of d{w) o(w) When dTi(w) < d(w) o(w) for every vertex w £ Ti, the vertex w appears in at most d(w) subforests Fi. Finally we use the subforests to define a subset F of edges of G. Let For any edge wx of Fi put the edge WiXi of G in the set F. By construction the set of edges F is a subforest of G, and maximal degree of a vertex in F is h(Ta). As F is bipartite, edges of F can be properly colored by h(Ta) colors as claimed. □ Hamiltonian. V(Ga). We construct a Hamilton cycle in X as in Theorem 4.2 of [3]. More precisely, recall that the vertices of the spanning tree Ta are the orbits 0(v,a). If 0(v, a) is a set of k vertices, then the subgraph of Cn\I\aG induced on the vertex set V(Cn) x 0{v,a) is isomorphic to a cycle Cnk or a Mobius ladder, i.e. a cycle Cnk with diagonals (as proved in [3]). Start with cycles corresponding to the orbits. Recall that given Ta, by Lemma 3.1 there exists a partial proper coloring of edges of G with h(Ta) colors. Now use the edges of F with the edge coloring to construct a Hamiltonian cycle as follows. If two orbits are adjacent, then by construction there is an edge e = WiXj of F that meets both orbits. If c ^ h(Ta) — 1, then the edge e and its color c define a 4-cycle in X which has one edge in each of the cycles and the other two edges correspond to the edge e in c-th copy and in (c + l)-th edge e in c-th copy of the fibre and to the edge a(wi)a(xj) in (c + l)-th copy of the fibre. Replacing the two edges of the 4-cycle by the other two parallel edges we get a cycle covering both orbits. Repeating this operation joins all the orbits and We illustrate the construction used in the proof by two examples. Example 3.3. Figure 3a) shows the graph G and the quotient graph Ga (Figure maxjl, , } = 2 and there exists a Hamiltonian cycle in bundle with n> 2. Note that the vertices of Ga represent orbits, i.e. cycles in C^n^G, one of them being isomorphic to C2, two to C4 and one to C4 with diagonals. We join this cycles into a Hamiltonian cycle using the three disjoint 4~cycles as in the proof of theorem we get the Hamiltonian cycle in Figure 2b). Example 3.4. Figure 4 shows: a)the graph G, b)the quotient graph Ga with the automorphism a = (5, 6)(7, 8) and c)the choosen spanning tree Ta. In this case is b)The quotient graph c)The two subforests F\ and F n + 1, then CnnaG is not Hamiltonian. Hamiltonian and let TL be a Hamiltonian cycle of X. Construct the set A as above to obtain a spanning tree Ta as shown in Lemma 3.5. By construction, each orbit is "encountered" at most once, and each time a vertex in the orbit is visited along the walk, another orbit may be "encountered", so the maximal valence of a vertex w £ Ta is mn + 1, where rri = o(w). Hence d(w) o(w) = \m7^] = \n+i]=n+ 1 8 irena hrastnik ladinek*, janez zerovnik** and the valence of the spanning tree Ta of Ga is at most n + 1. Therefore Let G be an arbitrary connected graph with maximum degree A(G) > 2 and let Aut(G) be the group of automorphisms of G. We define the number V(Ga)min as Using this notation, the statements of Theorems 3.2 and 3.6 can be written as Theorem 3.7. For any non-trivial connected graph G with A(G) > 2, Example 3.8. Now we turn back to Figure 3. All automorphisms of G are: a\ = For identity we have V(G^) = 3, which means that the Cartesian product CnnG Remark 3.9. Clearly, CnnaPi = CnQPi = Cn is Hamiltonian for any n. There is Hamiltonian for any n > 2 and Cn\JaP2 is Hamiltonian for any n. Hence [l [2 [3 [4 [5 [6 [7 [8 [9 [10 References Batagelj V.—Pisanski T.: Hamiltonian cycles in the cartesian product of a tree and a cycle, Discrete Math. 38, (1982), 311 - 312. Dimakopoulos V. V.—Palios L.—Poulakidas A.S.: On the hamiltonicity of the cartesian product, Information Processing Letters 96, (2005), 49 - 53. Pisanski, T.—Zerovnik, J.: Hamilton cycles in graph bundles over a cycle with tree as a fibre, Discrete Math. 309, (2009), 5432 - 5436. Imrich, W.—Klavzar, S.: Product Graphs, Structure and Recognition, John Wiley & Sons, New York, 2000. Mohar, B.—Pisanski, T.—Skoviera, M.: The maximum genus of graph bundles, Eur. J. Comb. 9, (1988), 301 - 314. Pisanski, T.—Vrabec, J.: Graph bundles, Prep. Ser. Dep. Math. 20, Ljubljana, 1982, 213 -298. Pisanski, T.—Shawe-Taylor, J.—Vrabec, J.: Edge-colorability of graph bundles, J. Comb. Theory Ser. B 35, (1983), 12 - 19. Zmazek, B.—Zerovnik, J.: Recognizing weighted directed Cartesian graph bundles, Discuss. Math. Graph Theory 20, (2000), 39 - 56. Zmazek, B.—Zerovnik, J.: Algorithm for recognizing Cartesian graph bundles, Discrete Appl. Math. 120, (2002), 275 - 302. Zmazek, B.—Zerovnik, J.: On domination numbers of graph bundles, Journal of Appl. Math, and Comput. 22, (2006), 39 - 48. [11] Zerovnik ,J.: On recognition of strong graph bundles, Math. Slovaca 50, (2000), 289 - 301 *,University of Maribor Faculty of Mechanical Engineering Smetanova 17 2000 Maribor Slovenia. E-mail address: irena.hrastnik@uni-mb. si **,University of Ljubljana Faculty of Mechanical Engineering Askerceva 6 1000 Ljubljana Slovenia **,Institute of Mathematics, Physics and Mechanics Jadranska 19 1000 Ljubljana Slovenia E-mail address: janez.zerovnik@imfm.uni-lj .si