The genus of repeated cartesian products of bipartite graphs

Abstract:

With the aid of techniques developed by Edmonds, Ringel, and Youngs, it is shown that the genus of the cartesian product of the complete bipartite graph ${K_{2m,2m}}$ with itself is $1 + 8{m^2}(m - 1)$. Furthermore, let $Q_1^{(s)}$ be the graph ${K_{s,s}}$ and recursively define the cartesian product $Q_n^{(s)} = Q_{n - 1}^{(s)} \times {K_{s,s}}$ for $n \geqq 2$. The genus of $Q_n^{(s)}$ is shown to be $1 + {2^{n - 3}}{s^n}(sn - 4)$, for all n, and s even; or for $n > 1$, and $s = 1 \; \text {or} \; 3$. The graph $Q_n^{(1)}$ is the 1-skeleton of the n-cube, and the formula for this case gives a result familiar in the literature. Analogous results are developed for repeated cartesian products of paths and of even cycles.