A proof of the crossing number of $K_{3,n}$ in a surface

ArticleOriginal scientific text

Title

Authors ¹

Department of Mathematics, MATH 1044, Purdue University, West Lafayette, IN 47907-2067, USA

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

K_{3, n}

in a surface with Euler genus ε is ⎣n/(2ε+2)⎦ {n - (ε+1)(1+⎣n/(2ε+2)⎦)}.

crossing number, bipartite graph, surface

R.K. Guy and T.A. Jenkyns, The toroidal crossing number of $K_{m, n}$ , J. Combin. Theory 6 (1969) 235-250, doi: 10.1016/S0021-9800(69)80084-0.
R.B. Richter and J. Siran, The crossing number of $K_{3, 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
G. Ringel, Das Geschlecht des vollständigen paaren Graphen, Abh. Math. Sem. Univ. Hamburg 28 (1965) 139-150, doi: 10.1007/BF02993245.
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.