Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



The genus of repeated cartesian products of bipartite graphs

Author: Arthur T. White
Journal: Trans. Amer. Math. Soc. 151 (1970), 393-404
MSC: Primary 05.50
MathSciNet review: 0281653
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 \;$   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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05.50

Retrieve articles in all journals with MSC: 05.50

Additional Information

Keywords: Genus of a graph, cartesian product of two graphs, bipartite graph, complete bipartite graph, path, cycle, n-cube, 2-manifold, Euler formula, Edmonds' permutation technique, quadrilateral imbedding, cyclomatic number of a graph
Article copyright: © Copyright 1970 American Mathematical Society

American Mathematical Society