Alternating cycles in edge-partitioned graphs

It is shown that if the edges of a 2-connected graph G are partitioned into two classes so that every vertex is incident with edges from both classes, then G has an alternating cycle. The connectivity assumption can be dropped if both subgraphs resulting from the partition are regular, or have only vertices of odd degree.     

Alternating cycles in edge-colored graphs

We show that the edges of a 2-connected graph can be partitioned into two color classes so that every vertex is incident with edges of each color and every alternating cycle passes through a single edge. We also show that the edges of a simple graph with minimum vertex degree δ ? 2 can be partitioned into three color classes so that every vertex is incident with edges in exactly two colors and no cycle is alternating.     

Hamiltonian cycles in polyhedral maps

We present a necessary and sufficient condition for existence of a contractible, non-separating and non-contractible separating Hamiltonian cycle in the edge graph of polyhedral maps on surfaces. We also present algorithms to construct such cycles whenever it exists where one of them is linear time and another is exponential time algorithm.     

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.     

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.     

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.     

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.     

Lexicographic matchings cannot form Hamiltonian cycles

For any positive integer k let B(k) denote the bipartite graph of k- and k+1-element subsets of a 2k+1-element set with adjacency given by containment. It has been conjectured that for all k, B(k) is Hamiltonian. Any Hamiltonian cycle would be the union of two (perfect) matchings. Here it is shown that for all k>1 no Hamiltonian cycle in B(k) is the union of two lexicographic matchings.Supported by Office of Naval Research Contract N00014-85-K-0769.Supported by NSERC grants 69-3378 and 69-0259.     

On extremal hypergraphs for Hamiltonian cycles

We study sufficient conditions for Hamiltonian cycles in hypergraphs, and obtain both Turán- and Dirac-type results. While the Turán-type result gives an exact threshold for the appearance of a Hamiltonian cycle in a hypergraph depending only on the extremal number of a certain path, the Dirac-type result yields a sufficient condition relying solely on the minimum vertex degree.     

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.     

Essential independent sets and Hamiltonian cycles

An independent set S of a graph G is said to be essential if S has a pair of vertices distance two apart in G. We prove that if every essential independent set S of order k ≥ 2 in a k-connected graph of order p satisfies max {deg v:v ϵ S} ≥ ½ p, then g is hamiltonian. This generalizes the result of Fan (J. Combinatorial Theory B 37 (1984), 221–227). If we consider the essential independent sets of order k + 1 instead of k in the assumption of the above statement, we can no longer assure the existence a hamiltonian cycle. However, we can still give a lower bound to the length of a longest cycle. © 1996 John Wiley & Sons, Inc.     

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.     

On pedigree polytopes and Hamiltonian cycles

In this paper we define a combinatorial object called a pedigree, and study the corresponding polytope, called the pedigree polytope. Pedigrees are in one-to-one correspondence with the Hamiltonian cycles on K_n. Interestingly, the pedigree polytope seems to differ from the standard tour polytope, Q_n with respect to the complexity of testing whether two given vertices of the polytope are nonadjacent. A polynomial time algorithm is given for nonadjacency testing in the pedigree polytope, whereas the corresponding problem is known to be NP-complete for Q_n. We also discuss some properties of the pedigree polytope and illustrate with examples.     

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 → ∞.     

Sums and differences along Hamiltonian cycles

Given a finite abelian group G, consider the complete graph on the set of all elements of G. Find a Hamiltonian cycle in this graph and for each pair of consecutive vertices along the cycle compute their sum. What are the smallest and the largest possible number of distinct sums that can emerge in this way? What is the expected number of distinct sums if the cycle is chosen randomly? How do the answers change if an orientation is given to the cycle and differences (instead of sums) are computed? We give complete solutions to some of these problems and establish reasonably sharp estimates for the rest.     

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.