Guy's Conjecture
Guy's conjecture, which has not yet been proven or disproven, states that the graph crossing number for a complete
graph of order 
is
 |
(1)
|
where 
is the floor
function, which can be rewritten
 |
(2)
|
The first few values are 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, ... (OEIS A000241).
Guy (1972) proved the conjecture for 
, a result
extended to 
by Pan and Richter (2007).
Guy, R. K. "Crossing Numbers of Graphs." In Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Mich., May 10-13, 1972 (Ed. Y. Alavi, D. R. Lick, and A. T. White). New York: Springer-Verlag, pp. 111-124, 1972.
Pan, S. and Richter, R. B. "The Crossing Number of 
is 100."
J. Graph Th. 56, 128-134, 2007.
Sloane, N. J. A. Sequence A000241/M2772 in "The On-Line Encyclopedia of Integer Sequences."
Weisstein, Eric W. "Guy's Conjecture." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GuysConjecture.html
Contact the MathWorld Team
vertex-transitive
graph
