In this paper we introduce a new class of partially filled arrays that, as Heffter arrays, are related to difference families, graph decompositions and biembeddings. A non-zero sum Heffter array NH(m, n; h, k) is an m x n p.f. array with entries in Z(2nk+1) such that: each row contains h filled cells and each column contains k filled cells; for every x is an element of Z(2nk+1) \ {0}, either x or -x appears in the array; the sum of the elements in every row and column is different from 0 (in Z(2nk+1)). Here first we explain the connections with relative difference families and with path decompositions of the complete multipartite graph. Then we present a complete solution for the existence problem and a constructive complete solution for the square case and for the rectangular case with no empty cells when the additional, very restrictive, property of being "globally simple " is required. Finally, we show how these arrays can be used to construct biembeddings of complete graphs. (C) 2022 Elsevier B.V. All rights reserved.
Non-zero sum Heffter arrays and their applications
Costa S.;Della Fiore S.;Pasotti A.
2022-01-01
Abstract
In this paper we introduce a new class of partially filled arrays that, as Heffter arrays, are related to difference families, graph decompositions and biembeddings. A non-zero sum Heffter array NH(m, n; h, k) is an m x n p.f. array with entries in Z(2nk+1) such that: each row contains h filled cells and each column contains k filled cells; for every x is an element of Z(2nk+1) \ {0}, either x or -x appears in the array; the sum of the elements in every row and column is different from 0 (in Z(2nk+1)). Here first we explain the connections with relative difference families and with path decompositions of the complete multipartite graph. Then we present a complete solution for the existence problem and a constructive complete solution for the square case and for the rectangular case with no empty cells when the additional, very restrictive, property of being "globally simple " is required. Finally, we show how these arrays can be used to construct biembeddings of complete graphs. (C) 2022 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
