The genus of repeated cartesian products of bipartite graphs
HTML articles powered by AMS MathViewer
- by Arthur T. White PDF
- Trans. Amer. Math. Soc. 151 (1970), 393-404 Request permission
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.References
- Lowell W. Beineke and Frank Harary, The genus of the $n$-cube, Canadian J. Math. 17 (1965), 494–496. MR 175805, DOI 10.4153/CJM-1965-048-6 J. Edmonds, A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. 7 (1960), 646. Abstract #572-1.
- Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911
- Gerhard Ringel, Über drei kombinatorische Probleme am $n$-dimensionalen Würfel und Würfelgitter, Abh. Math. Sem. Univ. Hamburg 20 (1955), 10–19 (German). MR 75586, DOI 10.1007/BF02960735
- Gerhard Ringel, Das Geschlecht des vollständigen paaren Graphen, Abh. Math. Sem. Univ. Hamburg 28 (1965), 139–150 (German). MR 189012, DOI 10.1007/BF02993245
- Gerhard Ringel and J. W. T. Youngs, Das Geschlecht des vollständigen dreifärbbaren Graphen, Comment. Math. Helv. 45 (1970), 152–158 (German). MR 262114, DOI 10.1007/BF02567322
- Gerhard Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968), 438–445. MR 228378, DOI 10.1073/pnas.60.2.438
- Arthur T. White, The genus of the complete tripartite graph $K_{mn,n,n}$, J. Combinatorial Theory 7 (1969), 283–285. MR 245470
- J. W. T. Youngs, Minimal imbeddings and the genus of a graph, J. Math. Mech. 12 (1963), 303–315. MR 0145512
Additional Information
- © Copyright 1970 American Mathematical Society
- 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