The crossing number of K1,m,n

A longstanding problem of crossing number, Zarankiewicz's conjecture, asserts that the crossing number of the complete bipartite graph K(m,n) is left perpendicular m/2 right perpendicular left perpendicular m-1/2 right perpendicular left perpendicular n/2 right perpendicular left perpendicular n-1/2 right perpendicular, which is known only for m <= 6. It is natural to generalize Zarankiewicz conjecture and ask: What is the crossing number for the complete multipartite graph? In this paper, we prove the following lower bounds for the corssing number of K(1,m,n) in terms of the corssing number of the complete bipartite graph: cr(K(1,m,n)) >= cr (K(m+1,n+1)) - left perpendicular n/m left perpendicular m/2 right perpendicular left perpendicular m+1/2 right perpendicular right perpendicular; cr(K(1,2M,n)) >= 1/2(cr(K(2M+1,n+2)) + cr(K(2M+1,n)) - M(M +n-1)). As a corollary, we show that: 1. cr(K(1,m,n)) >= 0.8594Z(m + 1,n + 1) - left perpendicular n/m left perpendicular m/2 right perpendicular left perpendicular m+1/2 right perpendicular right perpendicular; 2. If Zarankiewicz's conjecture is true for m = 2M + 1, then cr(K(1,2M,n)) = M(2) left perpendicular n+1/2 right perpendicular left perpendicular n/2 right perpendicular - M left perpendicular n/2 right perpendicular; 3. cr(K(1,4,n)) + 4 left perpendicular n+1/2 right perpendicular left perpendicular n/2 right perpendicular - 2 left perpendicular n/2 right perpendicular. (C) 2007 Elsevier B.V. All rights reserved.