Premium
Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
Author(s) -
Woodall D. R.
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170602
Subject(s) - combinatorics , conjecture , mathematics , bipartite graph , vertex (graph theory) , graph , crossing number (knot theory) , order (exchange) , transitive relation , discrete mathematics , intersection (aeronautics) , finance , engineering , economics , aerospace engineering
Zarankiewicz's conjecture, that the crossing number of the complete‐bipartite graph K m, n is [1/2 m ] [1/2 ( m ] −1) [1/2 n ] [1/2 ( n −1)], was proved by Kleitman when min( m, n ) ≤ 6, but was unsettled in all other cases. The cyclic‐order graph CO n arises naturally in the study of this conjecture; it is a vertex‐transitive harmonic diametrical (even) graph. In this paper the properties of cyclic‐order graphs are investigated and used as the basis for computer programs that have verified Zarankiewicz's conjecture for K 7,7 and K 7,9 ; thus the smallest unsettled cases are now K 7,11 and K 9,9 . © 1993 John Wiley & Sons, Inc.