On the stable crossing number of cubes
HTML articles powered by AMS MathViewer
- by Paul C. Kainen PDF
- Proc. Amer. Math. Soc. 36 (1972), 55-62 Request permission
Abstract:
Very few results are known which yield the crossing number of an infinite class of graphs on some surface. In this paper it is shown that by taking the class of graphs to be d-dimensional cubes $Q(d)$ and by allowing the genus of the surface to vary, we obtain upper and lower bounds on the crossing numbers which are independent of d. Specifically, if the genus of the surface is always $\gamma (Q(d)) - k$, where $\gamma (Q(d))$ is the genus of $Q(d)$ and k is a fixed nonnegative integer, then $4k \leqq \operatorname {cr}_{\gamma (Q(d)) - k} (Q(d)) \leqq 8k$ provided that k is not too large compared to d.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
- Paul C. Kainen, A lower bound for crossing numbers of graphs with applications to $K_{n}$, $K_{p,\,q}$, and $Q(d)$, J. Combinatorial Theory Ser. B 12 (1972), 287–298. MR 299515, DOI 10.1016/0095-8956(72)90042-1
- 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 E. C. Zeeman, Seminar on combinatorial topology, Chap. 2, Institut des Hautes Etudes Scientifiques, 1963 (mimeographed).
Additional Information
- © Copyright 1972 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 36 (1972), 55-62
- MSC: Primary 05C10
- DOI: https://doi.org/10.1090/S0002-9939-1972-0306028-7
- MathSciNet review: 0306028