The crossing number of the generalized Petersen graph P(3k,k) in the projective plane
Jing Wang, Zuozheng Zhang · AKCE International Journal of Graphs and Combinatorics · 2023
The crossing number of a graph G in a surface Σ, denoted by crΣ(G), is the minimum number of pairwise intersections of edges in a drawing of G in Σ. Let k be an integer satisfying k≥3, the generalized Petersen graph P(3k,k) is the graph with vertex set V(P(3k,k))={ui,vi∣i=1,2,…,3k} and edge set E(P(3k,k))={uiui+1,uivi,vivk+i∣i=1,2,…,3k}, the subscripts are read modulo 3k. In this paper we investigate the crossing number of P(3k,k) in the projective plane. We determine the exact value of crN1(P(3k,k)) is k–2 when 3≤k≤7, moreover, for k≥8, we get that k−2≤crN1(P(3k,k))≤k−1.