Skewness of generalized Petersen graphs and related graphs

Abstract

The skewness of a graph G is the minimum number of edges in G whose removal results in a planar graph. In this paper, we determine the skewness of the generalized Petersen graph P(4k, k) and hence a lower bound for the crossing number of P(4k, k). In addition, an upper bound for the crossing number of P(4k, k) is also given.

Keywords

Skewness / generalized Petersen graph / crossing number

References

[1] Chia G. L., Lee C. L. Crossing numbers and skewness of some Generalized Petersen graphs. Lecture Notes in Comput Sci, 2005, 3330: 80-86

[2] Chia G. L., Lee C. L. Skewness and crossing numbers of graphs. Bull Inst Combin Appl, 2009, 55: 17-32

[3] Fiorini S., Gausi J. B. The crossing number of the generalized Petersen graph P[3k, k]. Math Bohem, 2003, 128: 337-347

[4] Liu P. C., Geldmacher R. C. On the deletion of nonplanar edges of a graph. Congr Numer, 1979, 24: 727-738

[5] Salazar G. On the crossing numbers of loop networks and generalized Petersen graphs. Discrete Math, 2005, 302: 243-253