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

Abstract

ABSTRACTThe crossing number of a graph G in a surface Σ, denoted by [Formula: see text], is the minimum number of pairwise intersections of edges in a drawing of G in Σ. Let k be an integer satisfying [Formula: see text], the generalized Petersen graph [Formula: see text] is the graph with vertex set [Formula: see text] and edge set [Formula: see text] the subscripts are read modulo [Formula: see text] In this paper we investigate the crossing number of [Formula: see text] in the projective plane. We determine the exact value of [Formula: see text] is k–2 when [Formula: see text] moreover, for [Formula: see text] we get that [Formula: see text]

Keywords

• The projective plane
• crossing number
• the generalized Petersen graph
• drawing
• 05C10
• 05C62