On the stable crossing number of cubes

Kainen, Paul C.

doi:10.1090/S0002-9939-1972-0306028-7

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

Seminar on combinatorial topology