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.     

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 .     

Factorizations of complete multipartite graphs into generalized cubes

For a positive integer d, the usual d‐dimensional cube Q_d is defined to be the graph (K₂)^d, the Cartesian product of d copies of K₂. We define the generalized cube Q(K_k, d) to be the graph (K_k)^d for positive integers d and k. We investigate the decomposition of the complete multipartite graph K into factors that are vertex‐disjoint unions of generalized cubes Q(K_k, d_i), where k is a power of a prime, n and j are positive integers with j ≤ n, and the d_i may be different in different factors. We also use these results to partially settle a problem of Kotzig on Q_d‐factorizations of K_n. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000     

Edge‐transitive homogeneous factorizations of complete uniform hypergraphs

For a finite set V and a positive integer k with , letting be the set of all k‐subsets of V, the pair is called the complete k‐hypergraph on V, while each k‐subset of V is called an edge. A factorization of the complete k‐hypergraph of index , simply a ‐factorization of order n, is a partition of the edges into s disjoint subsets such that each k‐hypergraph , called a factor, is a spanning subhypergraph of . Such a factorization is homogeneous if there exist two transitive subgroups G and M of the symmetric group of degree n such that G induces a transitive action on the set and M lies in the kernel of this action. In this article, we give a classification of homogeneous factorizations of that admit a group acting transitively on the edges of . It is shown that, for and , there exists an edge‐transitive homogeneous ‐factorization of order n if and only if is one of (32, 3, 5), (32, 3, 31), (33, 4, 5), , and , where and q is a prime power with .     

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     

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     

Orthogonal factorizations of graphs

Let G be a graph with vertex set V(G) and edge set E(G). Let k₁, k₂,…,k_m be positive integers. It is proved in this study that every [0,k₁+…+k_m?m+1]‐graph G has a [0, k_i]₁^m‐factorization orthogonal to any given subgraph H with m edges. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 267–276, 2002     

Decomposition of complete graphs into 5‐cubes

Necessary conditions for the complete graph on n vertices to have a decomposition into 5‐cubes are that 5 divides n ? 1 and 80 divides n(n ? 1)/2. These are known to be sufficient when n is odd. We prove them also sufficient for n even, thus completing the spectrum problem for the 5‐cube and lending further weight to a long‐standing conjecture of Kotzig. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 159–166, 2006     

Star factorizations of graph products

A k‐star is the graph K_1,k. We prove a general theorem about k‐star factorizations of Cayley graphs. This is used to give necessary and sufficient conditions for the existence of k‐star factorizations of any power (K_q)^s of a complete graph with prime power order q, products C × C ×··· × C of k cycles of arbitrary lengths, and any power (C_r)^s of a cycle of arbitrary length. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 59–66, 2001     

Nilpotent 1‐factorizations of the complete graph

For which groups G of even order 2n does a 1‐factorization of the complete graph K_2n exist with the property of admitting G as a sharply vertex‐transitive automorphism group? The complete answer is still unknown. Using the definition of a starter in G introduced in 4 , we give a positive answer for new classes of groups; for example, the nilpotent groups with either an abelian Sylow 2‐subgroup or a non‐abelian Sylow 2‐subgroup which possesses a cyclic subgroup of index 2. Further considerations are given in case the automorphism group G fixes a 1‐factor. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Isomorphic factorizations of complete equipartite graphs

A complete equipartite graph is a complete multipartite graph such that the color classes are equinumerous. An isomorphic factorization of a graph is a partition of the line set into disjoint isomorphic parts. It is shown that an isomorphic factorization of the complete equipartite graph into t isomorphic subgraphs exists whenever the total number of lines is divisible by t.     

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     

Unbalanced bipartite factorizations of complete bipartite graphs

We construct a new infinite family of factorizations of complete bipartite graphs by factors all of whose components are copies of a (fixed) complete bipartite graph K_p,q. There are simple necessary conditions for such factorizations to exist. The family constructed here demonstrates sufficiency in many new cases. In particular, the conditions are always sufficient when q=p+1.     

A note on 3‐factorizations of K10*

In this note, we enumerate all nonisomorphic 3‐factorizations of K₁₀. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 379–383, 2001     

An algorithm for finding factorizations of complete graphs

We show how to find a decomposition of the edge set of the complete graph into regular factors where the degree and edge‐connectivity of each factor is prescribed. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 132–136, 2003     

Rainbow spanning trees in complete graphs colored by one‐factorizations

Brualdi and Hollingsworth conjectured that, for even n, in a proper edge coloring of using precisely colors, the edge set can be partitioned into spanning trees which are rainbow (and hence, precisely one edge from each color class is in each spanning tree). They proved that there always are two edge disjoint rainbow spanning trees. Krussel, Marshall, and Verrall improved this to three edge disjoint rainbow spanning trees. Recently, Carraher, Hartke and the author proved a theorem improving this to rainbow spanning trees, even when more general edge colorings of are considered. In this article, we show that if is properly edge colored with colors, a positive fraction of the edges can be covered by edge disjoint rainbow spanning trees.     

One‐factorizations of complete multigraphs and quadrics in PG(n,q)

A new infinite family of simple indecomposable one‐factorizations of the complete multigraphs is constructed by using quadrics of finite projective spaces. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 139–143, 2002; DOI 10.1002/jcd.997     

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