The Hamilton‐Waterloo problem for Hamilton cycles and triangle‐factors

In this article, we consider the Hamilton‐Waterloo problem for the case of Hamilton cycles and triangle‐factors when the order of the complete graph K_n is even. We completely solved the problem for the case n≡24 (mod 36). For the cases n≡0 (mod 18) and n≡6 (mod 36), we gave an almost complete solution. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 305–316, 2012     

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.     

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.     

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.     

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

A Generalization of the Hamilton–Waterloo Problem on Complete Equipartite Graphs

The Hamilton–Waterloo problem asks for which s and r the complete graph can be decomposed into s copies of a given 2‐factor F₁ and r copies of a given 2‐factor F₂ (and one copy of a 1‐factor if n is even). In this paper, we generalize the problem to complete equipartite graphs and show that can be decomposed into s copies of a 2‐factor consisting of cycles of length xzm; and r copies of a 2‐factor consisting of cycles of length yzm, whenever m is odd, , , and . We also give some more general constructions where the cycles in a given two factor may have different lengths. We use these constructions to find solutions to the Hamilton–Waterloo problem for complete graphs.     

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.     

On the spouse‐loving variant of the Oberwolfach problem

We prove that , the complete graph of even order with a 1‐factor duplicated, admits a decomposition into 2‐factors, each a disjoint union of cycles of length if and only if , except possibly when is odd and . In addition, we show that admits a decomposition into 2‐factors, each a disjoint union of cycles of lengths , whenever are all even.     

Completing the spectrum of almost resolvable cycle systems with odd cycle length

In this paper, we construct almost resolvable cycle systems of order $4k+1$ for odd $k\ge 11$. This completes the proof of the existence of almost resolvable cycle systems with odd cycle length. As a by-product, some new solutions to the Hamilton–Waterloo problem are also obtained.     

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.     

1‐rotational k‐factorizations of the complete graph and new solutions to the Oberwolfach problem

We consider k‐factorizations of the complete graph that are 1‐rotational under an assigned group G, namely that admit G as an automorphism group acting sharply transitively on all but one vertex. After proving that the k‐factors of such a factorization are pairwise isomorphic, we focus our attention to the special case of k = 2, a case in which we prove that the involutions of G necessarily form a unique conjugacy class. We completely characterize, in particular, the 2‐factorizations that are 1‐rotational under a dihedral group. Finally, we get infinite new classes of previously unknown solutions to the Oberwolfach problem via some direct and recursive constructions. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 87–100, 2008     

On bipartite 2‐factorizations of kn − I and the Oberwolfach problem

It is shown that if F₁, F₂, …, F_t are bipartite 2‐regular graphs of order n and α₁, α₂, …, α_t are positive integers such that α₁ + α₂ + ? + α_t = (n ? 2)/2, α₁≥3 is odd, and α_i is even for i = 2, 3, …, t, then there exists a 2‐factorization of K_n ? I in which there are exactly α_i 2‐factors isomorphic to F_i for i = 1, 2, …, t. This result completes the solution of the Oberwolfach problem for bipartite 2‐factors. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:22‐37, 2011     

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     

Line graphs of multigraphs and Hamilton‐connectedness of claw‐free graphs

We introduce a closure concept that turns a claw‐free graph into the line graph of a multigraph while preserving its (non‐)Hamilton‐connectedness. As an application, we show that every 7‐connected claw‐free graph is Hamilton‐connected, and we show that the well‐known conjecture by Matthews and Sumner (every 4‐connected claw‐free graph is hamiltonian) is equivalent with the statement that every 4‐connected claw‐free graph is Hamilton‐connected. Finally, we show a natural way to avoid the non‐uniqueness of a preimage of a line graph of a multigraph, and we prove that the closure operation is, in a sense, best possible. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:152‐173, 2011     

On stability of Hamilton‐connectedness under the 2‐closure in claw‐free graphs

It is easy to characterize chordal graphs by every k‐cycle having at least f(k) = k ? 3 chords. I prove new, analogous characterizations of the house‐hole‐domino‐free graphs using f(k) = 2?(k ? 3)/2?, and of the graphs whose blocks are trivially perfect using f(k) = 2k ? 7. These three functions f(k) are optimum in that each class contains graphs in which every k‐cycle has exactly f(k) chords. The functions 3?(k ? 3)/3? and 3k ? 11 also characterize related graph classes, but without being optimum. I consider several other graph classes and their optimum functions, and what happens when k‐cycles are replaced with k‐paths. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:137‐147, 2011     

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.     

1‐rotationally resolvable 4‐cycle systems of 2Kv

In this article, it is shown that there exists a 1‐rotationally resolvable 4‐cycle system of 2K_υ if and only if υ ≡ 0 (mod 4). To prove that, some special sequences of integers are utilized. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 116–125, 2002; DOI 10.1002/jcd.10006     

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is n‐HC‐extendable if it contains a path of length n and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is weakly n‐HP‐extendable if it contains a path of length n and if every such path is contained in some Hamilton path of Γ. Moreover, Γ is strongly n‐HP‐extendable if it contains a path of length n and if for every such path P there is a Hamilton path of Γ starting with P. These concepts are then studied for the class of connected Cayley graphs on abelian groups. It is proved that every connected Cayley graph on an abelian group of order at least three is 2‐HC‐extendable and a complete classification of 3‐HC‐extendable connected Cayley graphs of abelian groups is obtained. Moreover, it is proved that every connected Cayley graph on an abelian group of order at least five is weakly 4‐HP‐extendable. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory