The crossing numbers of generalized Petersen graphs with small order ?
The generalized Petersen graph P(n,k) P ( n , k ) is an undirected graph on 2n 2 n vertices with V(P(n,k))={ai,bi:0?i?n?1} V ( P ( n , k ) ) = { a i , b i : 0 ? i ? n ? 1 } and E(P(n,k))={aibi,aiai+1,bibi+k:0?i?n?1,subscriptsmodulon} E ( P ( n , k ) ) = { a i b i , a i a i + 1 , b i b i + k : 0 ? i ? n ? 1 , subscriptsmodulo n } . Fiorini claimed to have determined the crossing numbers of P(n,3) P ( n , 3 ) and showed all the values of cr(P(n,k)) c r ( P ( n , k ) ) for n n up to 14, except 12 unknown values. Lovre?i? Sarain proved cr(P(10,4))=cr(P(10,6))=4 c r ( P ( 10 , 4 ) ) = c r ( P ( 10 , 6 ) ) = 4 . Richter and Salazar found a gap in Fiorinis paper, which invalidated his principal results about cr(P(n,3)) c r ( P ( n , 3 ) ) , and gave the correct proof for cr(P(n,3)) c r ( P ( n , 3 ) ) . In this paper, we show the crossing numbers of all P(n,k) P ( n , k ) for n n up to 16.
crossing number generalized petersen graph planar graph embedding