کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646909 | 1342318 | 2015 | 5 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 338, Issue 7, 6 July 2015, Pages 1173–1177