Disproof of a conjecture by Erdős and Guy on the crossing number of hypercubes

Abstract

Let $Q_n$ be the $n$-dimensional hypercube, and let $\mathrm{cr}(Q_n)$ be the \textit{crossing number} of $Q_n$. Erdős and Guy in 1973 conjectured the following equality: $\mathrm{cr}(Q_n)=\frac{5}{32}{4}^n-\lfloor \frac{n^2+1}{2}\rfloor 2^{n-2}$. In this paper, we construct a drawing of $Q_n$ with less crossings when $n>6$, which implies that for $n>6$ we have a strict inequality.

44 pages; To appear in Journal of Graph Theory

Cited by in corpus (2)

• A survey of graphs with known or bounded crossing numbers
• An upper bound for the crossing number of augmented cubes