zbMATH — the first resource for mathematics

On Eggleton and Guy’s conjectured upper bound for the crossing number of the \(n\)-cube. (English) Zbl 0984.05027
Summary: The crossing number \(\nu(G)\) of a graph \(G\) is the smallest integer such that there is a drawing for \(G\) with \(\nu(G)\) crossings of edges. Let \(Q_n\) denote the \(n\)-dimensional cube. Eggleton and Guy conjectured in 1970 that \(\nu(Q_n) \leq 4^n\frac {5}{32} - 2^{n-2} \lfloor \frac {n^2+1}{2}\rfloor \).
We exhibit a drawing for \(n = 6\) with the same value of Eggleton and Guy’s conjectured upper bound. We construct a family of drawings for the \(n\)@-cubes, \(n \geq 7\), with number of crossings \(\frac {165}{1024}4^{n}-\frac {2n^2-11n+34}{2}2^{n-2}\), establishing a new upper bound for \(\nu(Q_n)\). Our family of drawings confirms Eggleton and Guy’s conjectured upper bound when \(n=7\) and \(8\). In addition, our upper bound improves the upper bound \(\nu(Q_n) \leq 4^n\frac {1}{6} - 2^{n-3}n^2 - 2^{n-4}3 + (-2)^n\frac {1}{48}\) due to Madej.

05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: EuDML
[1] DEAN A. M.-RICHTER R. B.: The crossing number of C4 x C4. J. Graph Theory 19 (1995), 125-129.
[2] EGGLETON R. B.-GUY R. P.: The crossing number of the n-cube. Notices Amer. Math. Soc. 17 (1970), 757.
[3] ERDÖS P.-GUY R. P.: Crossing number problems. Amer. Math. Monthly 80 (1973), 52-58. · Zbl 0264.05109
[4] FARIA L.: Bounds for the crossing number of the n-cube. Master thesis, Universidade Federal do Rio de Janeiro, 1994.
[5] GAREY M. R.-JOHNSON D. S.: Crossing number is NP-complete. SIAM J. Discrete Math. 4 (1983), 312-316. · Zbl 0536.05016
[6] GUY R. P.: Latest results on crossing numbers. Proc. Recent Trends in Graph theory. Lecture Notes in Math. 186, Springer, New York, 1971, pp. 143-156. · Zbl 0217.02303
[7] MADEJ T.: Bounds for the crossing number of the n-cube. J. Graph Theory 15 (1991), 81-97. · Zbl 0722.05028
[8] RINGEISEN R. D.-BEINEKE L. W.: The crossing number of C3 x Cn. J. Combin. Theory Ser. B 24 (1978), 134-136. · Zbl 0383.05015
[9] SÝKORA O.-VRŤO I.: On the crossing number of hypercubes and cube connected cycles. BIT 33 (1993), 232-237. · Zbl 0780.68002
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.