 Open Access
 Total Downloads : 21
 Authors : M. Malathi , Dr. J. Ravi Sankar ,
 Paper ID : IJERTCONV3IS22024
 Volume & Issue : NCEASE – 2015 (Volume 3 – Issue 22)
 Published (First Online): 24042018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
The Bounds of Crossing Number in Complete Bipartite Graphs
M. Malathi Department of Mathematics Saradha Gangadharan College Pondicherry, India 605 004.
Dr. J. Ravi Sankar
School of Advanced Sciences VIT University
Vellore, India 632 014.
Dr. N. Selvi Department of Mathematics
ADM College for Women, Nagapattinam, India611001
AbstractWe compare the lower bound of crossing number of bipartite and complete bipartite graph with Zarankiewicz conjecture and we illustrate the possible upper bound by a
II A MODIFIED ZARANKIEWICZ CONJECTURE:
For any complete bipartite graphs with n vertices,
modified Zarankiewicz conjecture.
1 n 2 n n
n n
Keywordscomplete bipartite graphs, crossing numbers
Z (n, n)
2 2
2 2 1 2 2 1

INTRODUCTION
Let G = (V,E) be a simple connected graph with vertex set V(G) and edge set E(G).
The crossing number of a graph G, denoted by Cr(G), is the minimum number of crossings in a drawing of G in the plane[2,3,4].
The crossing number of the complete bipartite graph [7] was first introduced by Paul Turan, by his brick factory problem.
In 1954, Zarankiewicz conjectured [8] that,
By using this conjecture, we can get all the possible number of crossings between every vertices for a given n, without any good drawing D. This reverse way of finding the crossings facilitates for large n by without drawing the graph, we can get all possible crossings between every edges.
The best known lower bound on general case for all m,n N which was proved by D.J.Kleitman [1] in the following theorem. That is,
Theorem1[6]:
n n 1
m m 1 n n 1
cr(K5,n ) 4 2 2
Z(m,n) = 2
2 2
2
cr(K
) 6 n n 1
Where m and n are vertices.
Later, Richard Guy shown that the conjecture doesnot holds for all m,n. Then in 1970 D.J.Kleitman proved that
6,n
From this he deduced that
2 2
Zarankiewicz conjecture holds for Min(m,n) 6.
cr(K
) 1 m(m 1) n n 1
A good drawing of a graph G is a drawing where the edges are nonselfintersecting in which any two edges have atmost one point in common other than end vertex. That is, a crossing is a point of intersection of two edges and no three edges
m,n 5
Theorem2:
2 2
intersect at a common point. So a good drawing is a crossing free drawing by arriving at a planar graph.
The crossing number is an important measure of the non planarity of a graph. Therefore this application can be widely
For m > n, cr Z (m, n) cr Km,n cr Kn,m .
Proof:
From theorem 1,
applied in all real time problems.
cr(K
) 1 m(m 1) n n 1
m,n 5
2 2
By definition,
Z(m,n) = m m 1 n n 1
cr Z (5, 4) 2.2.2.1 8
5
5
cr K 1 .5.4.2.1 8
2 2 2 2
5,4
We can prove the theorem byinduction. Since in
cr K
1 .4.3.2.2 48 9.8
cr Km,n , there are c K subgraphs of K with the
m
5 5,n
5 5,n
m,n
4,5 5 5
partite with n vertices in K5,n . So we shall obtain the lower
cr Z (5, 4) cr K5,4 cr K4,5
bound of cr Km,n for m 5 and n 3. Case(i): Let n=3.
Subcase(ii): m=6,
cr Z (6, 4) 3.2.2.1 12
Subcase(i): m=5,
cr Z (5, 3) 2.2.1.1 4 1
cr K
cr K
6,4
1 .6.5.2.1 12
5
1 .4.3.3.2 72 14.4
cr K
5,3
.5.4.1.1 4
5
4,6 5 5
cr K3,5
1 .3.2.2.2 24 4.8
5 5
cr Z (6, 4) cr K6,4 cr K4,6
Subcase(ii): m=7,
cr Z (5, 3) cr K5,3 cr K3,5
cr Z (7, 4) 3.3.2.1 18
Subcase(ii): m=6,
cr Z (6, 3) 3.2.1.1 6
cr K
7,4
1 .7.6.2.1 84 16.8
5 5
1 108
cr K6,3
1 .6.5.1.1 6
cr K4,7 .4.3.3.3
21.6
5
5
5
5
5 cr Z (7, 4) cr K7,4 cr K4,7
3,6
3,6
1 36
cr K .3.2.3.2 7.2
5 5
cr Z (m, 4) cr K
m,4 cr K4,m
cr Z (6, 3) cr K
6,3 cr K3,6
In general,
cr Z (m, n) cr K
m,n cr Kn,m .
Subcase(ii): m=7,
cr Z (7, 3) 3.3.1.1 9
We also observe that the following inequality ,
2cr Z (m, n 1) 2cr Km,n1 2cr Kn1,m
cr K
7,3
1 .7.6.1.1 42 8.4
5 5
Also holds good for the above cases. Hence the proof.
cr K
3,7
1 .3.2.3.3 54 10.8
5 5
Theorem 2:
cr Z (7, 3) cr K
cr K
For m = n, cr Z (m, n) cr Km,n .That is,
7,3 3,7
1 n 2 n n n n
cr Z (m, 3) cr Km,3 cr K3,m
2 2 2 2 1 2 2 1
Case(ii): Let n=4.
n 4 1 n n 1
Subcase(i): m=5,
2
Proof:
n(n 1)
5 2 2
When m = n, Z (n, n) is a complete bipartite graph.
By theorem 1,
cr K
1 n(n 1) n n 1
m,n 5
2
2
We shall prove the theorem for large sufficiently larger n and hence deducing the result for subsequent small n.
Case(i):
cr K9,9 256
1 4(4)2 3(4)2 3(4)2 3(4)2 3(4)2
2 4(4)2 4(4)2 4(4)2 4(4)2
cr K11,11 625
1 5(5)2 4(5)2 4(5)2 4(5)2 4(5)2 4(5)2 1 (4)2 5.4 4.3
2
2 5(5)2 5(5)2 5(5)2 5(5)2 5(5)2
1 n 2 n n
n n
1 (5)2 6.5 5.4
2 2
2 2 1 2 2 1
2
3
1 n 2 n n n n
1 n 2 n
1 1
2 2
2
2 2
3
3
1 n
2 2
2 n
2 2
n 4
2
2 2 2
n 4
2
cr Z (9,9) cr K
In general,
9,9
cr Z (11,11) 550 1 .11.10.5.5
5
1 .11(111) 11 111
5 2 2
cr Z (m, n) cr Km,n
Hence the proof.
III CONCLUSION
We have given an alternate way of finding crossings in complete bipartite graphs. We also proved in bipartite
graphs, the best lower bound of cr Km,n will always be a
1 .n(n 1) n n 1
lower bound until m and n are altered.
5 2 2
cr Z (11,11) cr K11,11
Case(ii):
REFERENCES
cr Z (9, 9) 256
1
1 .9.8.4.4
5
9 9 1

Daniel J. Kleitman, The crossing number of K5,n, J. Combinatorial Theory 9(1970),315323.

D.R. Woodall, Cyclicorder graph and Zarankiewicz's crossing number conjecture, J.Graph Theory. 17 (1994), 657671.
5 9(9 1) 2 2
1 .n(n 1) n n 1
5 2 2

P. Erdos, R.P. Guy, Crossing number problem, American Mathematical Monthly 80 (1973), 5258.

R.K. Guy, The decline and fall of Zarankiewicz's theorem, Proof techniques in Graph Theory, F. Harary, ed. Academic Press, New York(1969),6369.

R.K. Guy and T. Jenkins, The toroidal crossing number of Km;n, J. CombinatorialTheory.6(1969),235250.

N.H. Nahas, On the crossing number of Km;n. Electron. J. Combin, 10:N8,(2003).

R. Bruce Richter, Carsten Thomassen, Relations between crossing numbers of complete and complete bipartite graphs,The American Mathematical Monthly104 (1997),131137.

K. Zarankiewicz, On a problem of P. Turan concerning graphs, Fund. Math. 41 (1954),137145.