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.     

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     

Rotational k‐cycle systems of order v < 3k; another proof of the existence of odd cycle systems

We give an explicit solution to the existence problem for 1‐rotational k‐cycle systems of order v < 3k with k odd and v ≠ 2k + 1. We also exhibit a 2‐rotational k‐cycle system of order 2k + 1 for any odd k. Thus, for k odd and any admissible v < 3k there exists a 2‐rotational k‐cycle system of order v. This may also be viewed as an alternative proof that the obvious necessary conditions for the existence of odd cycle systems are also sufficient. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 433–441, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10061     

Symmetric Hamilton cycle decompositions of the complete graph

We construct a new symmetric Hamilton cycle decomposition of the complete graph K_n for odd n > 7. © 2003 Wiley Periodicals, Inc.     

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.     

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 .     

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     

Large sets of Hamilton cycle and path decompositions

The existence spectrums for large sets of Hamilton cycle decompositions and Hamilton path decompositions are completed. Also, we show that the completion of large sets of directed Hamilton cycle decompositions and directed Hamilton path decompositions depends on the existence of certain special tuscan squares. Several conjectures about special tuscan squares are posed.     

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     

Large Sets of Wrapped K–K Hamilton Cycle Decompositions of Complete Bipartite 3‐Uniform Hypergraphs

Using the Katona–Kierstead (K–K) definition of a Hamilton cycle in a uniform hypergraph, we investigate the existence of wrapped K–K Hamilton cycle decompositions of the complete bipartite 3‐uniform hypergraph and their large sets, settling their existence whenever n is prime.     

A complete solution to the existence problem for 1‐rotational k‐cycle systems of Kv

The necessary and sufficient conditions for the existence of a 1‐rotational k‐cycle system of the complete graph K_v are established. The proof provides an algorithm able to determine, directly and explicitly, an odd k‐cycle system of K_v whenever such a system exists. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 283–293, 2009     

Decompositions of complete graphs into triangles and Hamilton cycles

For all odd integers n ≥ 1, let G_n denote the complete graph of order n, and for all even integers n ≥ 2 let G_n denote the complete graph of order n with the edges of a 1‐factor removed. It is shown that for all non‐negative integers h and t and all positive integers n, G_n can be decomposed into h Hamilton cycles and t triangles if and only if nh + 3t is the number of edges in G_n. © 2004 Wiley Periodicals, Inc.     

On Hamilton decompositions of infinite circulant graphs

The natural infinite analog of a (finite) Hamilton cycle is a two‐way‐infinite Hamilton path (connected spanning 2‐valent subgraph). Although it is known that every connected 2k‐valent infinite circulant graph has a two‐way‐infinite Hamilton path, there exist many such graphs that do not have a decomposition into k edge‐disjoint two‐way‐infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2k‐valent connected circulant graph has a decomposition into k edge‐disjoint Hamilton cycles. We settle the problem of decomposing 2k‐valent infinite circulant graphs into k edge‐disjoint two‐way‐infinite Hamilton paths for , in many cases when , and in many other cases including where the connection set is or .     

Hamilton cycle decompositions of the tensor product of complete multipartite graphs

In this paper, tensor product of two regular complete multipartite graphs is shown to be Hamilton cycle decomposable. Using this result, it is immediate that the tensor product of two complete graphs with at least three vertices is Hamilton cycle decomposable thereby providing an alternate proof of this fact.     

6‐regular 4‐critical graph

P. Erd?s conjectured in [2] that r‐regular 4‐critical graphs exist for every r ≥ 3 and noted that no such graphs are known for r ≥ 6. This article contains the first example of a 6‐regular 4‐critical graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 286–291, 2002     

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     

On large sets of almost Hamilton cycle decompositions

A large set of CS(v, k, λ), k‐cycle system of order v with index λ, is a partition of all k‐cycles of K_v into CS(v, k, λ)s, denoted by LCS(v, k, λ). A (v ? 1)‐cycle is called almost Hamilton. The completion of the existence spectrum for LCS(v, v ? 1, λ) only depends on one case: all v ≥ 4 for λ = 2. In this article, it is shown that there exists an LCS(v, v ? 1,2) for any v ≡ 0,1 (mod 4) except v = 5, and for v = 6,7,10,11. © 2006 Wiley Periodicals, Inc. J Combin Designs 16: 53–69, 2008     

Almost regular edge colorings and regular decompositions of complete graphs

For k = 1 and k = 2, we prove that the obvious necessary numerical conditions for packing t pairwise edge‐disjoint k‐regular subgraphs of specified orders m₁,m₂,… ,m_t in the complete graph of order n are also sufficient. To do so, we present an edge‐coloring technique which also yields new proofs of various known results on graph factorizations. For example, a new construction for Hamilton cycle decompositions of complete graphs is given. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 499–506, 2008     

The nonexistence of a (K6‐e)‐decomposition of the complete graph K29

We show via an exhaustive computer search that there does not exist a (K₆?e)‐decomposition of K₂₉. This is the first example of a non‐complete graph G for which a G‐decomposition of K_2|E(G)|+1 does not exist. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 94–104, 2010