The minimum orientable genus of the repeated Cartesian product of graphs
Marietta Galea, John Baptist Gauci · Journal of Combinatorial Optimization · 2025
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)}$$ Q i ( s ) is obtained by taking the repeated Cartesian product of i complete bipartite graphs $$K_{s,s}$$ K s , 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.