Biembeddings of cycle systems using integer Heffter arrays

Abstract

In this paper, we use constructions of Heffter arrays to verify the existence of face 2-colorable embeddings of cycle decompositions of the complete graph. Specifically, forn degrees 1(mod 4)andk degrees 3(mod4),n >> k > 7and whenn degrees 0(mod 3)thenk degrees 7(mod 12), there exist face 2-colorable embeddings of the complete graphK2nk+1onto an orientable surface where each face is a cycle of a fixed lengthk. In these embeddings the vertices ofK2nk+1will be labeled with the elements ofZ2nk+1in such a way that the group,(Z2nk+1,+)acts sharply transitively on the vertices of the embedding. This result is achieved by verifying the existence of nonequivalent Heffter arrays,H(n;k), which satisfy the conditions: (1) for each row and each column the sequential partial sums determined by the natural ordering must be distinct modulo2nk+1; (2) the composition of the natural orderings of the rows and columns is equivalent to a single cycle permutation on the entries in the array. The existence of Heffter arraysH(n;k)that satisfy condition (1) was established earlier in Burrage et al. and in this current paper, we vary this construction and show, fork > 11, that there are at least(n-2)[((k-11)/4)!/e]2such nonequivalentH(n;k)that satisfy both conditions (1) and (2).