The crossing number of the generalized Petersen graph $P(3k,k)$ in the projective plane

Wang Jing; Zhang Zuozheng

paper

The crossing number of the generalized Petersen graph $P (3 k, k)$ in the projective plane

arXiv:2104.11640

Abstract

The crossing number of a graph $G$ in a surface $Σ$ , denoted by $c r_{Σ} (G)$ , is the minimum number of pairwise intersections of edges in a drawing of $G$ in $Σ$ . Let $k$ be an integer satisfying $k \geq 3$ , the generalized Petersen graph $P (3 k, k)$ is the graph with vertex set $V (P (3 k, k)) = {u_{i}, v_{i} ∣ i = 1, 2, \dots, 3 k}$ and edge set $E (P (3 k, k)) = {u_{i} u_{i + 1}, u_{i} v_{i}, v_{i} v_{k + i} ∣ i = 1, 2, \dots, 3 k},$ the subscripts are read modulo $3 k .$ This paper investigates the crossing number of $P (3 k, k)$ in the projective plane. We determine the exact value of $c r_{N_{1}} (P (3 k, k))$ is $k - 2$ when $3 \leq k \leq 7,$ moreover, for $k \geq 8,$ we get that $k - 2 \leq c r_{N_{1}} (P (3 k, k)) \leq k - 1.$

The crossing number of the generalized Petersen graph P(3k,k) in the projective plane

Abstract

The crossing number of the generalized Petersen graph $P (3 k, k)$ in the projective plane