Discussiones Mathematicae Graph Theory 27(3) (2007) 549-551
doi: 10.7151/dmgt.1379

[BIBTex] [PDF] [PS]

A PROOF OF THE CROSSING NUMBER OF K3,n IN A SURFACE

Pak Tung Ho

Department of Mathematics, MATH 1044
Purdue University
West Lafayette, IN 47907-2067, USA
e-mail: pho@math.purdue.edu

Abstract

In this note we give a simple proof of a result of Richter and Siran by basic counting method, which says that the crossing number of K3,n in a surface with Euler genus ε is

n
2ε+2



n−(ε+1)
1+
n
2ε+2


⎫>

.

Keywords: crossing number, bipartite graph, surface.

2000 Mathematics Subject Classification: 05C10.

References

[1] R.K. Guy and T.A. Jenkyns, The toroidal crossing number of Km,n, J. Combin. Theory 6 (1969) 235-250, doi: 10.1016/S0021-9800(69)80084-0.
[2] R.B. Richter and J. Siran, The crossing number of K3,n in a surface, J. Graph Theory 21 (1996) 51-54, doi: 10.1002/(SICI)1097-0118(199601)21:1<51::AID-JGT7>3.0.CO;2-L.
[3] G. Ringel, Das Geschlecht des vollständigen paaren Graphen, Abh. Math. Sem. Univ. Hamburg 28 (1965) 139-150, doi: 10.1007/BF02993245.
[4] G. Ringel, Der vollständige paare Graph auf nichtorientierbaren Flächen, J. Reine Angew. Math. 220 (1965) 88-93, doi: 10.1515/crll.1965.220.88.

Received 11 September 2006
Accepted 21 March 2007