info prev up next book cdrom email home

Guy's Conjecture

Guy's conjecture, which has not yet been proven or disproven, states that the Crossing Number for a Complete Graph of order $n$ is

\begin{displaymath}
{1\over 4}\left\lfloor{n\over 2}\right\rfloor \left\lfloor{n...
...2\over 2}\right\rfloor \left\lfloor{n-3\over 2}\right\rfloor ,
\end{displaymath}

where $\left\lfloor{x}\right\rfloor $ is the Floor Function, which can be rewritten

\begin{displaymath}
\cases{
{\textstyle{1\over 64}} n(n-2)^2(n-4) & for $n$\ even\cr
{\textstyle{1\over 64}} (n-1)^2(n-3)^2 & for $n$\ odd.\cr}
\end{displaymath}

The first few values are 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, ... (Sloane's A000241).

See also Crossing Number (Graph)


References

Sloane, N. J. A. Sequence A000241/M2772 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.




© 1996-9 Eric W. Weisstein
1999-05-25