Guy,s Conjecture
المؤلف:
Brodsky, A.; Durocher, S.; and Gethner, E
المصدر:
"The Rectilinear Crossing Number of K_(10) Is 62." 22 Sep 2000.
الجزء والصفحة:
...
3-4-2022
1753
Guy's Conjecture
Guy's conjecture, which has not yet been proven or disproven, states that the graph crossing number for a complete graph 
is
 |
(1)
|
where 
is the floor function, which can be rewritten
![Z(n)=<span style=]() {1/(64)n(n-2)^2(n-4) for n even; 1/(64)(n-1)^2(n-3)^2 for n odd. " src="https://mathworld.wolfram.com/images/equations/GuysConjecture/NumberedEquation2.svg" style="height:61px; width:253px" /> |
(2)
|
The values for 
, 2, ... are then given by 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315, 441, 588, ... (OEIS A000241).
Guy (1972) proved the conjecture for 
, a result extended to 
by Pan and Richter (2007).
It is known that
 |
(3)
|
(Richter and Thomassen 1997, de Klerk et al. 2007, Pan and Richter 2007).
REFERENCES
Brodsky, A.; Durocher, S.; and Gethner, E. "The Rectilinear Crossing Number of 
Is 62." 22 Sep 2000.
http://arxiv.org/abs/cs/0009023.de Klerk, E.; Pasechnik, D. V.; and Schrijver, A. "Reduction of Symmetric Semidefinite Programs Using the Regular 
-Representation." Math Program. 109, 613-624, 2007
.de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. "Improved Bounds for the Crossing Numbers of 
and 
." 2004.
https://arxiv.org/pdf/math/0404142.pdf.Guy, R. K. "The Crossing Number of the Complete Graph." Bull. Malayan Math. Soc. 7, 68-72, 1960.
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."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
