Fair holey hamiltonian decompositions of complete multipartite graphs and long cycle frames

A kk-factor   of a graph G=(V(G),E(G))G=(V(G),E(G)) is a kk-regular spanning subgraph of GG. A kk-factorization   is a partition of E(G)E(G) into kk-factors. Let K(n,p)K(n,p) be the complete multipartite graph with pp parts, each of size nn. If V1,…,VpV1,…,Vp are the pp parts of V(K(n,p))V(K(n,p)), then a holey     kk-factor   of deficiency ViVi of K(n,p)K(n,p) is a kk-factor of K(n,p)−ViK(n,p)−Vi for some ii satisfying 1≤i≤p1≤i≤p. Hence a holey  kk-factorization   is a set of holey kk-factors whose edges partition E(K(n,p))E(K(n,p)). A holey hamiltonian decomposition   is a holey 2-factorization of K(n,p)K(n,p) where each holey 2-factor is a connected subgraph of K(n,p)−ViK(n,p)−Vi for some ii satisfying 1≤i≤p1≤i≤p. A (holey) kk-factorization of K(n,p)K(n,p) is said to be fair   if the edges between each pair of parts are shared as evenly as possible among the permitted (holey) factors. In this paper the existence of fair holey hamiltonian decompositions of K(n,p)K(n,p) is completely settled. This result simultaneously settles the existence of cycle frames of type npnp for cycles of the longest length, being a companion for results in the literature for frames with short cycle length.