×

A new view of hypercube genus. (English) Zbl 1464.05268

Summary: L. W. Beineke and F. Harary [Can. J. Math. 17, 494–496 (1965; Zbl 0127.13801)] discovered a formula for the minimum genus of a torus in which the \(n\)-dimensional hypercube graph can be embedded. We give a new proof of the formula by building this surface as a union of certain faces in the hypercube’s 2-skeleton. For odd dimension \(n\), the entire 2-skeleton decomposes into (\(n-1\))/2 copies of the surface, and the intersection of any two copies is the hypercube graph.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
57M15 Relations of low-dimensional topology with graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory

Citations:

Zbl 0127.13801
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, B., The wonderful Walecki construction, Bull. Inst. Combin. Appl, 52, 7-20 (2008) · Zbl 1157.05035
[2] Beineke, L. W.; Harary, F., The genus of the n-cube, Canad. J. Math, 17, 494-496 (1965) · Zbl 0127.13801 · doi:10.4153/CJM-1965-048-6
[3] Chartrand, G.; Lesniak, L.; Zhang, P., Graphs and Digraphs (2011), Boca Raton, FL: Chapman & Hall/CRC Press, Boca Raton, FL · Zbl 1211.05001
[4] Coxeter, H. S. M., Regular skew polyhedra in three and four dimensions and their topological anaolgues, Proc. Lond. Math. Soc, 43, 2, 33-62 (1937) · JFM 63.0584.03 · doi:10.1112/plms/s2-43.1.33
[5] Das, S., Genus of the hypercube graph and real moment-angle complexes, Topol. Appl, 258, 415-424 (2019) · Zbl 1409.05067 · doi:10.1016/j.topol.2019.03.009
[6] Goodman, S. E., Beginning Topology (2005), Pacific Grove, CA: Thompson Brooks/Cole, Pacific Grove, CA
[7] Hammack, R. H.; Kainen, P. C., Sphere decompositions of hypercubes, Art Discr. Appl. Math, 3, 2 (2020) · Zbl 1447.05170
[8] Harary, F., Graph Theory (1969), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0182.57702
[9] Hunter, R.; Kainen, P. C., Quadrilateral embedding of \(####\), Bull. Inst. Combin. Appl., 52, 13-20 (2007) · Zbl 1137.05022
[10] Jungerman, M., The non-orientable genus of the n-cube, Pacific J. Math, 76, 2, 443-451 (1978) · Zbl 0386.05026
[11] Kainen, P. C., On the stable crossing number of cubes, Proc. Amer. Math. Soc, 36, 1, 55-62 (1972) · Zbl 0253.05118
[12] Kainen, P. C.; White, A. T., On stable crossing numbers, J. Graph Theory, 2, 3, 181-187 (1978) · Zbl 0401.05039 · doi:10.1002/jgt.3190020302
[13] Pisanski, T., Orientable quadrilateral embeddings of products of graphs. Algebraic graph theory, Discrete Math, 109, 1-3, 203-205 (1989) · Zbl 0780.05018
[14] Pisanski, T., Genus of Cartesian products of regular bipartite graphs, J. Graph Theory, 4, 1, 31-42 (1980) · Zbl 0432.05024 · doi:10.1002/jgt.3190040105
[15] Ringel, G., Über drei kombinatorische Probleme am n-dimensionalen Würfel und Würfelgitter, Abh. Math. Sem. Univ. Hamburg, 20, 10-19 (1955) · Zbl 0065.16703
[16] Ringel, G., Das Gescshlecht des vollständgen parren Graphen, Abh. Math. Sem. Univ. Hamburg, 28, 139-150 (1965) · Zbl 0132.21203 · doi:10.1007/BF02993245
[17] Ringel, G.; Youngs, J. W. T., Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. USA, 60, 438-445 (1968) · Zbl 0155.51201 · doi:10.1073/pnas.60.2.438
[18] Robbin, T., Cubism and Modern Thought, Shadows of Reality: The Fourth Dimension in Relativity (2006), New Haven & London: Yale Univ. Press, New Haven & London
[19] White, A. T., The genus of repeated cartesian products of bipartite graphs, Trans. Amer. Math. Soc., 151, 393-404 (1970) · Zbl 0202.23401 · doi:10.1090/S0002-9947-1970-0281653-3
[20] Ziegler, G. M., Series: Graduate Texts in Mathematics, 152, Lectures on Polytopes (1994), New York: Springer-Verlag, New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.