Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



On the stable crossing number of cubes

Author: Paul C. Kainen
Journal: Proc. Amer. Math. Soc. 36 (1972), 55-62
MSC: Primary 05C10
MathSciNet review: 0306028
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [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] P. 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 0299515 (45:8563)
  • [3] 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)
  • [4] E. C. Zeeman, Seminar on combinatorial topology, Chap. 2, Institut des Hautes Etudes Scientifiques, 1963 (mimeographed).

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C10

Retrieve articles in all journals with MSC: 05C10

Additional Information

Keywords: Crossing number, genus, immersion, square immersion, cube, cogenus
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society