The minimum orientable genus of the repeated Cartesian product of families of graphs

Determining the minimum genus of a graph is a fundamental optimisation problem in the study of network design and implementation as it gives a measure of non-planarity of graphs. In this paper, we are concerned with determining the smallest value of g such that a given graph G has an embedding on the orientable surface of genus g. In particular, we consider the Cartesian product of graphs since this is a well studied graph operation which is often used for modelling interconnection networks. The s-cube Qᵢ⁽ˢ⁾ is obtained by taking the repeated Cartesian product of i complete bipartite graphs Ks,s. We determine the genus of the Cartesian product of the $2r$-cube with the repeated Cartesian product of cycles and of the Cartesian product of the $2r$-cube with the repeated Cartesian product of paths.