The minimum orientable genus of the repeated Cartesian product of graphs

期刊论文
出版模式：

开放获取
发表日期：

2025年2月20日

查看全文

Marietta Galea,
John Baptist Gauci

摘要

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.