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, for n ≡ 1 (mod 4) and k ≡3(mod 4), n k ≫ ⩾ 7 and when n ≡ 0(mod 3) then k ≡ 7(mod 12), there exist face 2-colorable embeddings of the complete graph K₂ₙₖ₊₁ onto an orientable surface where each face is a cycle of a fixed length k. In these embeddings the vertices of K₂ₙₖ₊₁ will be labeled with the elements of Z₂ₙₖ₊₁ in such a way that the group, (Z₂ₙₖ₊₁, +) 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 modulo 2nk + 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 arrays H (n ; k) that satisfy condition (1) was established earlier in Burrage et al. and in this current paper, we vary this construction and show, for k ⩾ 11, that there are at least (n − 2)[((k − 11)/4)!/ ]² such nonequivalent H (n ; k) that satisfy both conditions (1) and (2).