Genus of cartesian products of regular bipartite graphs
Tomaž Pisanski · Journal of Graph Theory · 1980
Abstract Let G(n, d) denote a connected regular bipartite graph on 2n vertices and of degree d. It is proved that any Cartesian product G(n, d) × G1(n1, d1) × G2(n2, d2) × ⃛ × Gm(nm, dm), such that max {d1, d2,…, dm} ≤ d ≤ d1 + d2 + ⃛ + dm, has a quadrilateral embedding, thereby establishing its genus, and thereby generalizing a result of White. It is also proved that if G is any connected bipartite graph of maximum degree D, if Qm is the m‐cube graph, and if m ≥ D then G × Qm has a quadrilateral embedding.