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 Free Access

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

DOI: https://doi.org/10.1090/S0002-9947-1970-0281653-3
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