The Bounds of Crossing Number in Complete Bipartite Graphs

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, India-611001

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

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 non-self-intersecting 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

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

2. D.R. Woodall, Cyclic-order graph and Zarankiewicz's crossing number conjecture, J.Graph Theory. 17 (1994), 657-671.

   5 9(9 1) 2 2

   1 .n(n 1) n n 1

   5 2 2

3. P. Erdos, R.P. Guy, Crossing number problem, American Mathematical Monthly 80 (1973), 52-58.

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

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

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

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

8. K. Zarankiewicz, On a problem of P. Turan concerning graphs, Fund. Math. 41 (1954),137-145.