The Hamilton–Waterloo Problem for ‐Factors and ‐Factors

The Hamilton–Waterloo problem asks for a 2‐factorization of (for v odd) or minus a 1‐factor (for v even) into ‐factors and ‐factors. We completely solve the Hamilton–Waterloo problem in the case of C₃‐factors and ‐factors for .     

On the Hamilton‐Waterloo Problem for Bipartite 2‐Factors

Given two 2‐regular graphs F₁ and F₂, both of order n, the Hamilton‐Waterloo Problem for F₁ and F₂ asks for a factorization of the complete graph into α₁ copies of F₁, α₂ copies of F₂, and a 1‐factor if n is even, for all nonnegative integers α₁ and α₂ satisfying . We settle the Hamilton‐Waterloo Problem for all bipartite 2‐regular graphs F₁ and F₂ where F₁ can be obtained from F₂ by replacing each cycle with a bipartite 2‐regular graph of the same order.     

Further results on almost resolvable cycle systems and the Hamilton–Waterloo problem

In this paper, we almost completely solve the existence of almost resolvable cycle systems with odd cycle length. We also use almost resolvable cycle systems as well as other combinatorial structures to give some new solutions to the Hamilton–Waterloo problem.     

Hamilton cycle rich two‐factorizations of complete graphs

For all integers n ≥ 5, it is shown that the graph obtained from the n‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n. This result is used to prove several results on 2‐factorizations of the complete graph K_n of order n. For example, it is shown that for all odd n ≥ 11, K_n has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n, and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n, the corresponding result is proved for the graph K_n ‐ I obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc.     

On the Hamilton–Waterloo problem with odd cycle lengths

Let denote the complete graph if v is odd and , the complete graph with the edges of a 1‐factor removed, if v is even. Given nonnegative integers , the Hamilton–Waterloo problem asks for a 2‐factorization of into α ‐factors and β ‐factors, with a ‐factor of being a spanning 2‐regular subgraph whose components are ℓ‐cycles. Clearly, , , and are necessary conditions. In this paper, we extend a previous result by the same authors and show that for any odd the above necessary conditions are sufficient, except possibly when , or when . Note that in the case where v is odd, M and N must be odd. If M and N are odd but v is even, we also show sufficiency but with further possible exceptions. In addition, we provide results on 2‐factorizations of the complete equipartite graph and the lexicographic product of a cycle with the empty graph.     

Hourglasses and Hamilton cycles in 4‐connected claw‐free graphs

We show that if G is a 4‐connected claw‐free graph in which every induced hourglass subgraph S contains two non‐adjacent vertices with a common neighbor outside S, then G is hamiltonian. This extends the fact that 4‐connected claw‐free, hourglass‐free graphs are hamiltonian, thus proving a broader special case of a conjecture by Matthews and Sumner. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 267–276, 2005     

The Hamilton–Waterloo problem for cycle sizes 3 and 4

The Hamilton–Waterloo problem seeks a resolvable decomposition of the complete graph K_n, or the complete graph minus a 1‐factor as appropriate, into cycles such that each resolution class contains only cycles of specified sizes. We completely solve the case in which the resolution classes are either all 3‐cycles or 4‐cycles, with a few possible exceptions when n=24 and 48. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 342–352, 2009     

The Hamilton–Waterloo Problem with even cycle lengths

The Hamilton–Waterloo Problem $\mathrm{HWP}(v;m,n;\alpha ,\beta )$ asks for a 2-factorization of the complete graph $K_v$ or $K_v?I$, the complete graph with the edges of a 1-factor removed, into $\alpha$ $C_m$-factors and $\beta$ $C_n$-factors, where $3\le m<n$. In the case that $m$ and $n$ are both even, the problem has been solved except possibly when $1\in \{\alpha ,\beta \}$ or when $\alpha$ and $\beta$ are both odd, in which case necessarily $v\equiv 2(mod4)$. In this paper, we develop a new construction that creates factorizations with larger cycles from existing factorizations under certain conditions. This construction enables us to show that there is a solution to $\mathrm{HWP}(v;2m,2n;\alpha ,\beta )$ for odd $\alpha$ and $\beta$ whenever the obvious necessary conditions hold, except possibly if $\beta =1$; $\beta =3$ and $gcd(m,n)=1$; $\alpha =1$; or $v=2mn∕gcd(m,n)$. This result almost completely settles the existence problem for even cycles, other than the possible exceptions noted above.     

Hamilton cycles in claw-heavy graphs

A graph G on n≥3 vertices is called claw-heavy if every induced claw (K_1,3) of G has a pair of nonadjacent vertices such that their degree sum is at least n. In this paper we show that a claw-heavy graph G has a Hamilton cycle if we impose certain additional conditions on G involving numbers of common neighbors of some specific pair of nonadjacent vertices, or forbidden induced subgraphs. Our results extend two previous theorems of Broersma, Ryjá?ek and Schiermeyer [H.J. Broersma, Z. Ryjá?ek, I. Schiermeyer, Dirac’s minimum degree condition restricted to claws, Discrete Math. 167-168 (1997) 155-166], on the existence of Hamilton cycles in 2-heavy graphs.     

Hamilton cycles in 3‐out

Let G_3‐out denote the random graph on vertex set [n] in which each vertex chooses three neighbors uniformly at random. Note that G_3‐out has minimum degree 3 and average degree 6. We prove that the probability that G_3‐out is Hamiltonian goes to 1 as n tends to infinity. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the Hamilton–Waterloo Problem with Odd Orders

Given nonnegative integers , the Hamilton–Waterloo problem asks for a factorization of the complete graph into α ‐factors and β ‐factors. Without loss of generality, we may assume that . Clearly, v odd, , , and are necessary conditions. To date results have only been found for specific values of m and n. In this paper, we show that for any integers , these necessary conditions are sufficient when v is a multiple of and , except possibly when or 3. For the case where we show sufficiency when with some possible exceptions. We also show that when are odd integers, the lexicographic product of with the empty graph of order n has a factorization into α ‐factors and β ‐factors for every , , with some possible exceptions.     

A note on the 2-power of Hamilton cycles

We determine the maximum number of edges of a graph without containing the 2-power of a Hamilton cycle. This extends a well-known theorem of Ore in 1961 concerning the maximum number of edges of a graph without containing a Hamilton cycle.     

Hamilton cycle decomposition of 6‐regular circulants of odd order

The circulant G = C(n,S), where , is the graph with vertex set Z_n and edge set . It is shown that for n odd, every 6‐regular connected circulant C(n, S) is decomposable into Hamilton cycles. © 2006 Wiley Periodicals, Inc. J Combin Designs     

Symmetric Hamilton cycle decompositions of complete graphs minus a 1‐factor

Let n≥2 be an integer. The complete graph K_n with a 1‐factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K_n−F has a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor F if and only if n≡2, 4 mod 8. We also show that the complete bipartite graph K_{n, n} has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1‐factor of K_{n, n}, then K_{n, n}−F has a symmetric Hamilton cycle decomposition if and only if n is odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010     

Hamilton paths and cycles in vertex-transitive graphs of order

It is shown that every connected vertex-transitive graph of order 6p, where p is a prime, contains a Hamilton path. Moreover, it is shown that, except for the truncation of the Petersen graph, every connected vertex-transitive graph of order 6p which is not genuinely imprimitive contains a Hamilton cycle.     

Vertex‐Transitive Graphs of Prime‐Squared Order Are Hamilton‐Decomposable

We prove that all connected vertex‐transitive graphs of order p², p a prime, can be decomposed into Hamilton cycles.     

Hamilton cycles and paths in vertex-transitive graphs—Current directions

In this article current directions in solving Lovász’s problem about the existence of Hamilton cycles and paths in connected vertex-transitive graphs are given.     

On factors of 4‐connected claw‐free graphs*

We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian, i.e., has a connected 2‐factor. Conjecture 2 (Matthews and Sumner): Every 4‐connected claw‐free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass‐free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 125–136, 2001     

Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles

If G is a graph and is a set of subgraphs of G, then an edge‐coloring of G is called ‐polychromatic if every graph from gets all colors present in G. The ‐polychromatic number of G, denoted , is the largest number of colors such that G has an ‐polychromatic coloring. In this article, is determined exactly when G is a complete graph and is the family of all 1‐factors. In addition is found up to an additive constant term when G is a complete graph and is the family of all 2‐factors, or the family of all Hamiltonian cycles.