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

2021/04/23 by Jing, Wang, Zuozheng, Zhang
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2104.11640

Abstract

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))=\u_i, v_i| i=1,2,⋯,3k\ and edge set E(P(3k,k))=\u_iu_i+1, u_iv_i, v_iv_k+i| i=1,2,⋯,3k\, the subscripts are read modulo 3k. This paper investigates the crossing number of P(3k,k) in the projective plane. We determine the exact value of cr_N1(P(3k,k)) is k-2 when 3≤ k≤ 7, moreover, for k≥ 8, we get that k-2≤ cr_N1(P(3k,k))≤ k-1.

Related

• The crossing number of the generalized Petersen graph P(10, 3) is six
• The Crossing Number of Circulant Graph C(3k+1;1,k) on the Projective Plane
• The crossing numbers of K_n,n-nK₂, K_n× P₂, K_n× P₃ and K_n× C₄
• The crossing numbers of K_m× P_n and K_m× C_n
• Crossing Number of 3-Plane Drawings