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

  • [1] L. W. Beineke and F. Harary, The genus of the n-cube, Canad. J. Math. 17 (1965), 494-496. MR 31 #81. MR 0175805 (31:81)
  • [2] J. Edmonds, A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. 7 (1960), 646. Abstract #572-1.
  • [3] F. Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969. MR 0256911 (41:1566)
  • [4] G. Ringel, Über drei kombinatorische Probleme am n-dimensionalen Würfel und Würfelgitter, Abh. Math. Sem. Univ. Hamburg 20 (1955), 10-19. MR 17, 772. MR 0075586 (17:772h)
  • [5] -, Das Geschlecht des vollständigen paaren Graphen, Abh. Math. Sem. Univ. Hamburg 28 (1965), 139-150. MR 32 #6439. MR 0189012 (32:6439)
  • [6] G. Ringel and J. W. T. Youngs, Das Geschlecht des Symmetrische Vollständige Drei-Farbaren Graphen, Comment. Math. Helv. (to appear). MR 0262114 (41:6724)
  • [7] -, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968), 438-445. MR 37 #3959. MR 0228378 (37:3959)
  • [8] A. T. White. The genus of the complete tripartite graph $ {K_{mn,n,n}}$, J. Combinatorial Theory 7 (1969), 283-285. MR 0245470 (39:6778)
  • [9] J. W. T. Youngs, Minimal imbeddings and the genus of a graph, J. Math. Mech. 12 (1963), 303-315. MR 26 #3043. MR 0145512 (26:3043)

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

American Mathematical Society