The minimum orientable genus of the repeated Cartesian product of graphs

Abstract 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 modeling interconnection networks. The s -cube $$Q_i^{(s)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>Q</mml:mi> <mml:mi>i</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>s</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msubsup> </mml:math> is obtained by taking the repeated Cartesian product of i complete bipartite graphs $$K_{s,s}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>,</mml:mo> <mml:mi>s</mml:mi> </mml:mrow> </mml:msub> </mml:math> . We determine the genus of the Cartesian product of the 2 r -cube with the repeated Cartesian product of cycles and of the Cartesian product of the 2 r -cube with the repeated Cartesian product of paths.