The crossing number of C(n; {1, ⌊n/2⌋ - 1})

Abstract

Calculating the crossing number of a given graph is, in general, an elusive problem. As Garey and Johnson have proved, the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing numbers of very few families of graphs are known exactly. Richter and Salazar studied the crossing number of the generalized Petersen graph and proved that cr(P(3h, 3)) = h (h ≥ 4); cr(P(3h + 1, 3)) = h + 3 (h ≥ 3); cr(P(3h + 2, 3)) = h + 2 (h ≥ 2). In this paper we study the crossing number of the circulant graph C(n; {1, ⌊n/2⌋ - 1}) and prove that cr(C(n; {1, n/2 - 1})) = n/2 for even n ≥ 8. For odd n ≥ 13, we give an upper bound and a relevant conjecture.