Relative Heffter arrays and biembeddings

Simone Costa, Anita Pasotti, Marco Antonio Pellegrini


Relative Heffter arrays, denoted by Ht(m, n; s, k), have been introduced as a generalization of the classical concept of Heffter array. A Ht(m, n; s, k) is an m × n partially filled array with elements in ℤv, where v = 2nk + t, whose rows contain s filled cells and whose columns contain k filled cells, such that the elements in every row and column sum to zero and, for every x ∈ ℤv not belonging to the subgroup of order t, either x or  − x appears in the array. In this paper we show how relative Heffter arrays can be used to construct biembeddings of cyclic cycle decompositions of the complete multipartite graph $K_{\frac{2nk+t}{t}\times t}$ into an orientable surface. In particular, we construct such biembeddings providing integer globally simple square relative Heffter arrays for t = k = 3, 5, 7, 9 and $n\equiv 3 \pmod 4$ and for k = 3 with t = n, 2n, any odd n.


Heffter array, biembedding, multipartite complete graph.

Full Text:


ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications