Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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 Free Access

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] Lowell W. Beineke and Frank Harary, The genus of the 𝑛-cube, Canad. J. Math. 17 (1965), 494–496. MR 0175805 (31 #81)
  • [2] Paul C. Kainen, A lower bound for crossing numbers of graphs with applications to 𝐾_{𝑛}, 𝐾_{𝑝,𝑞}, and 𝑄(𝑑), J. Combinatorial Theory Ser. B 12 (1972), 287–298. MR 0299515 (45 #8563)
  • [3] Gerhard Ringel, Über drei kombinatorische Probleme am 𝑛-dimensionalen Würfel und Würfelgitter, Abh. Math. Sem. Univ. Hamburg 20 (1955), 10–19 (German). 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

DOI: http://dx.doi.org/10.1090/S0002-9939-1972-0306028-7
PII: S 0002-9939(1972)0306028-7
Keywords: Crossing number, genus, immersion, square immersion, cube, cogenus
Article copyright: © Copyright 1972 American Mathematical Society