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

Cube factorizations of complete graphs

A cube factorization of the complete graph on n vertices, K_n, is a 3‐factorization of K_n in which the components of each factor are cubes. We show that there exists a cube factorization of K_n if and only if n ≡ 16 (mod 24), thus providing a new family of uniform 3‐factorizations as well as a partial solution to an open problem posed by Kotzig in 1979. © 2004 Wiley Periodicals, Inc.     

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.     

Hamilton cycle decompositions of the tensor products of complete bipartite graphs and complete multipartite graphs

In this paper, it is shown that the tensor product of the complete bipartite graph, K_r,r,r≥2, and the regular complete multipartite graph, , is Hamilton cycle decomposable.     

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.     

Hamilton connectivity of line graphs and claw‐free graphs

Let G be a graph and let V₀ = {ν∈ V(G): d_G(ν) = 6}. We show in this paper that: (i) if G is a 6‐connected line graph and if |V₀| ≤ 29 or G[V₀] contains at most 5 vertex disjoint K₄'s, then G is Hamilton‐connected; (ii) every 8‐connected claw‐free graph is Hamilton‐connected. Several related results known before are generalized. © 2005 Wiley Periodicals, Inc. J Graph Theory     

One‐factorizations of complete graphs with vertex‐regular automorphism groups

We consider one‐factorizations of K_2n possessing an automorphism group acting regularly (sharply transitively) on vertices. We present some upper bounds on the number of one‐factors which are fixed by the group; further information is obtained when equality holds in these bounds. The case where the group is dihedral is studied in some detail, with some non‐existence statements in case the number of fixed one‐factors is as large as possible. Constructions both for dihedral groups and for some classes of abelian groups are given. © 2002 John Wiley & Sons, Inc. J Combin Designs 10: 1–16, 2002     

Enclosings of decompositions of complete multigraphs in 2‐factorizations

Let k, m, n, λ, and μ be positive integers. A decomposition of into edge‐disjoint subgraphs is said to be enclosed by a decomposition of into edge‐disjoint subgraphs if and, after a suitable labeling of the vertices in both graphs, is a subgraph of and is a subgraph of for all . In this paper, we continue the study of enclosings of given decompositions by decompositions that consist of spanning subgraphs. A decomposition of a graph is a 2‐factorization if each subgraph is 2‐regular and spanning, and is Hamiltonian if each subgraph is a Hamiltonian cycle. We give necessary and sufficient conditions for the existence of a 2‐factorization of that encloses a given decomposition of whenever and . We also give necessary and sufficient conditions for the existence of a Hamiltonian decomposition of that encloses a given decomposition of whenever and either or and , or , , and .     

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     

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.     

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.     

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     

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     

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 .     

Some new results on 1‐rotational 2‐factorizations of the complete graph

It is known that a necessary condition for the existence of a 1‐rotational 2‐factorization of the complete graph K_2n+1 under the action of a group G of order 2n is that the involutions of G are pairwise conjugate. Is this condition also sufficient? The complete answer is still unknown. Adapting the composition technique shown in Buratti and Rinaldi, J Combin Des, 16 (2008), 87–100, we give a positive answer for new classes of groups; for example, the groups G whose involutions lie in the same conjugacy class and having a normal subgroup whose order is the greatest odd divisor of |G|. In particular, every group of order 4t+2 gives a positive answer. Finally, we show that such a composition technique provides 2‐factorizations with a rich group of automorphisms. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 237–247, 2010     

Resolvable gregarious cycle decompositions of complete equipartite graphs

The complete multipartite graph K_n(m) with n parts of size m is shown to have a decomposition into n-cycles in such a way that each cycle meets each part of K_n(m); that is, each cycle is said to be gregarious. Furthermore, gregarious decompositions are given which are also resolvable.     

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 isomorphic factorizations of circulant graphs

We investigate the conjecture that every circulant graph X admits a k‐isofactorization for every k dividing |E(X)|. We obtain partial results with an emphasis on small values of k. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 406–414, 2006