Longest cycles in polyhedral graphs

A sequence of polyhedral graphsG _n is constructed, having only 3-valent and 8-valent vertices and having only 3-gons and 8-gons as faces with the property that the shortness exponent of the sequence as well as the shortness exponent of the sequence of duals is smaller than one.     

3-Trees in polyhedral maps

We show that the vertices of the graph of any polyhedral map on the projective plane, torus or Klein bottle can be covered by a subgraph that is a tree of maximum valence 3. This extends a theorem of the author, who previously proved this theorem for the graphs of 3-dimensional polytopes. Several theorems dealing with paths in polyhedral maps are a consequence of these theorems.     

Alternating Hamiltonian cycles

Colour the edges of a complete graph withn vertices in such a way that no vertex is on more thank edges of the same colour. We prove that for everyk there is a constantc _ksuch that ifn>c _kthen there is a Hamiltonian cycle with adjacent edges having different colours. We prove a number of other results in the same vein and mention some unsolved problems.     

Two Hamiltonian cycles

If the line graph of a graph G decomposes into Hamiltonian cycles, what is G? We answer this question for decomposition into two cycles.     

Hamiltonian cycles in k-partite graphs

Chen et al determined the minimum degree threshold for which a balanced $k$-partite graph has a Hamiltonian cycle. We give an asymptotically tight minimum degree condition for Hamiltonian cycles in arbitrary $k$-partite graphs in that all parts have at most $n/2$ vertices (a necessary condition). To do this, we first prove a general result that both simplifies the process of checking whether a graph $G$ is a robust expander and gives useful structural information in the case when $G$ is not a robust expander. Then we use this result to prove that any $k$-partite graph satisfying the minimum degree condition is either a robust expander or else contains a Hamiltonian cycle directly.     

Hamiltonian cycles in bipartite graphs

We give a sufficient condition for bipartite graphs to be Hamiltonian. The condition involves the edge-density and balanced independence number of a bipartite graph.     

Hamiltonian cycles in -circulant digraphs

Let D be the circulant digraph with n vertices and connection set {2,3,c}. (Assume D is loopless and has outdegree 3.) Work of S. C. Locke and D. Witte implies that if n is a multiple of 6, c{(n/2)+2,(n/2)+3}, and c is even, then D does not have a hamiltonian cycle. For all other cases, we construct a hamiltonian cycle in D.     

Hamiltonian cycles in Dirac graphs

We prove that for any n-vertex Dirac graph (graph with minimum degree at least n/2) G=(V,E), the number, Ψ(G), of Hamiltonian cycles in G is at least

$exp_2 [2h(G) - n\log e - o(n)],$

where h(G)=maxΣ _e x _e log(1/x _e ), the maximum over x: E → ?⁺ satisfying Σ _e?υ x _e = 1 for each υ ∈ V, and log =log₂. (A second paper will show that this bound is tight up to the o(n).)

We also show that for any (Dirac) G of minimum degree at least d, h(G) ≥ (n/2) logd, so that Ψ(G) > (d/(e + o(1))) ⁿ . In particular, this says that for any Dirac G we have Ψ(G) > n!/(2 + o(1)) ⁿ , confirming a conjecture of G. Sárközy, Selkow, and Szemerédi which was the original motivation for this work.     

Hamiltonian cycles in generalized petersen graphs

Watkins (J. Combinatorial Theory 6 (1969), 152–164) introduced the concept of generalized Petersen graphs and conjectured that all but the original Petersen graph have a Tait coloring. Castagna and Prins (Pacific J. Math. 40 (1972), 53–58) showed that the conjecture was true and conjectured that generalized Petersen graphs G(n, k) are Hamiltonian unless isomorphic to G(n, 2) where n ≡ 5(mod 6). The purpose of this paper is to prove the conjecture of Castagna and Prins in the case of coprime numbers n and k.     

Hamiltonian paths and cycles in hypertournaments

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V| = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A$ contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertournament is merely an (ordinary) tournament. A path is a sequence v₁a₁v₂v₃···v_t−1v_t of distinct vertices v₁, v₂,⋖, v_t and distinct arcs a₁, ⋖, a_t−1 such that v_i precedes v_t−1 in a, 1 ≤ i ≤ t − 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as v_i's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, y ≡ V. We prove that every k-hypertournament on n (k) vertices has a Hamiltonian path (an extension of Redeis theorem on tournaments) and every strong k-hypertournament with n (k + 1) vertices has a Hamiltonian cycle (an extension of Camions theorem on tournaments). Despite the last result, it is shown that the Hamiltonian cycle problem remains polynomial time solvable only for k ≤ 3 and becomes NP-complete for every fixed integer k ≥ 4. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 277–286, 1997     

Hamiltonian cycles in 2-connected claw-free-graphs

M. Matthews and D. Sumner have proved that of G is a 2-connected claw-free graph of order n such that δ ≧ (n ? 2)/3, then G is hamiltonian. We prove that the bound for the minimum degree δ can be reduced to n/4 under the additional condition that G is not in F, where F is the set of all graphs defined as follows: any graph H in F can be decomposed into three vertex disjoint subgraphs H₁, H₂, H₃ such that , where u_i, v_i ? V(H_i), u_j v_j ? V(H_j) 1 ? i ≦ j ≦ 3. Examples are given to show that the bound n/4 is sharp. © 1995 John Wiley & Sons, Inc.     

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/loglogn)}=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^Ω(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+loglogn))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)k^Ω(1), running in time O(n²) for planar graphs.     

Hamiltonian cycles in cayley color graphs

A group Γ is said to possess a hamiltonian generating set if there exists a minimal generating set Δ for Γ such that the Cayley color graph D_Δ(Γ) is hamiltonian. It is shown that every finite abelian group has a hamiltonian generating set. Certain classes of nonabelian groups are also investigated.     

Hamiltonian cycles in 1-tough graphs

For a graphG, let ₃ = min{ _i=1 ³ d(u_i): {u₁, u₂, u₃} is an independent set ofG} and = min{ _i=1 ³ d(u_i) – is an independent set ofG}. In this paper, we shall prove the following result: LetG be a 1-tough graph withn vertices such that ₃ n and – 4. ThenG is hamiltonian. This generalizes a result of Fassbender [2], a result of Flandrin, Jung and Li [3] and a result of Jung [5].Supported in part by das promotionsstipendium nach dem NaFöG and the Post-Doctoral Foundation of China.     

Hamiltonian cycles in random regular graphs

The existence of Hamiltonian cycles in random vertex-labelled regular graphs is investigated. It is proved that there exists r₀≤796 such that for r≥r₀ almost all vertex-labelled r-regular graphs with n vertices have Hamiltonian cycles as n → ∞.     

Hamiltonian cycles and 2-dominating induced cycles in claw-free graphs

Let G = (V, E) be a connected graph. For a vertex subset , G[S] is the subgraph of G induced by S. A cycle C (a path, respectively) is said to be an induced cycle (path, respectively) if G[V(C)] = C (G[V(P)] = P, respectively). The distance between a vertex x and a subgraph H of G is denoted by , where d(x, y) is the distance between x and y. A subgraph H of G is called 2-dominating if d(x, H) ≤ 2 for all . An induced path P of G is said to be maximal if there is no induced path P′ satisfying and . In this paper, we assume that G is a connected claw-free graph satisfying the following condition: for every maximal induced path P of length p ≥ 2 with end vertices u, v it holds:

Distributing vertices on Hamiltonian cycles

Let G be a graph of order n and 3≤t≤n/4 be an integer. Recently, Kaneko and Yoshimoto [J Combin Theory Ser B 81(1) (2001), 100–109] provided a sharp δ(G) condition such that for any set X of t vertices, G contains a hamiltonian cycle H so that the distance along H between any two vertices of X is at least n/2t. In this article, minimum degree and connectivity conditions are determined such that for any graph G of sufficiently large order n and for any set of t vertices X?V(G), there is a hamiltonian cycle H so that the distance along H between any two consecutive vertices of X is approximately n/t. Furthermore, the minimum degree threshold is determined for the existence of a hamiltonian cycle H such that the vertices of X appear in a prescribed order at approximately predetermined distances along H. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 28–45, 2012     

A remark on Hamiltonian cycles

Every 2-connected graph G with $\text{δ ? (v + κ)}\text{3}$ is hamiltonian where v denotes the order, δ the minimum degree and κ the point connectivity of G.     

Multicolored parallelisms of Hamiltonian cycles

A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this paper, we prove that a complete graph on 2m+1 vertices K_2m+1 can be properly edge-colored with 2m+1 colors in such a way that the edges of K_2m+1 can be partitioned into m multicolored Hamiltonian cycles.