Let Kdenote the complete graph consisting of n vertices,every pair of which forms an edge.We want to know the least possible number of the intersections,when we draw the graph Kon the plane or on the sphere using cont...Let Kdenote the complete graph consisting of n vertices,every pair of which forms an edge.We want to know the least possible number of the intersections,when we draw the graph Kon the plane or on the sphere using continuous arcs for edges.In a paper published in 1960,Richard K.Guy conjectured that the least possible number of the intersections is 1/64(n-1)^(2)(n-3)^(2) if n is odd,or 1/64 n(n-2)^(2)(n-4)if n is even.A virgin road V_(n)is a drawing of a Hamiltonian cycle in Kconsisting of n vertices and n edges such that no other edge-representing arcs cross V.A drawing of Kis called virginal if it contains a virgin road.All drawings considered in this paper will be virginal with respect to a fixed virgin road V.We will present a certain drawing of a subgraph of K,for each n(≥5),which is"characteristic"in the sense that any minimal virginal drawing of Kcontaining this subdrawing satisfies Guy’s conjecture.展开更多
文摘Let Kdenote the complete graph consisting of n vertices,every pair of which forms an edge.We want to know the least possible number of the intersections,when we draw the graph Kon the plane or on the sphere using continuous arcs for edges.In a paper published in 1960,Richard K.Guy conjectured that the least possible number of the intersections is 1/64(n-1)^(2)(n-3)^(2) if n is odd,or 1/64 n(n-2)^(2)(n-4)if n is even.A virgin road V_(n)is a drawing of a Hamiltonian cycle in Kconsisting of n vertices and n edges such that no other edge-representing arcs cross V.A drawing of Kis called virginal if it contains a virgin road.All drawings considered in this paper will be virginal with respect to a fixed virgin road V.We will present a certain drawing of a subgraph of K,for each n(≥5),which is"characteristic"in the sense that any minimal virginal drawing of Kcontaining this subdrawing satisfies Guy’s conjecture.
