CYCLIC-ORDER GRAPHS AND ZARANKIEWICZS CROSSING-NUMBER CONJECTURE

Zarankiewicz's conjecture, that the crossing number of the complete-bi partite graph K-m,K-n is [1/2 m][1/2(m - 1)][1/2(n - 1)], was proved b y Kleitman when min(m, n) less than or equal to 6, but was unsettled i n all other cases. The cyclic-order graph COn arises naturally in the study of this conjecture; it is a vertex-transitive harmonic diametric al (even) graph. In this paper the properties of cyclic-order graphs a re investigated and used as the basis for computer programs that have verified Zarankiewicz's conjecture for K-7,K-7 and K-7,K-9; thus the s mallest unsettled cases are now K-7,K-11 and K-9,K-9. (C) 1993 John Wi ley and Sons, Inc.