Frontiers of Mathematics in China >

2012 , Vol. 7 >Issue 3: 427 - 436

DOI: https://doi.org/10.1007/s11464-012-0186-5

RESEARCH ARTICLE

Skewness of generalized Petersen graphs and related graphs

  • Gek Ling CHIA ,
  • Chan Lye LEE
Expand
  • Institute of Mathematical Sciences, University of Malaya, 50603 Kuala Lumpur, Malaysia

Received date: 28 Oct 2010

Accepted date: 21 Dec 2011

Published date: 01 Jun 2012

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg
Fold

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.

Key words： Skewness; generalized Petersen graph; crossing number

Cite this article

Gek Ling CHIA , Chan Lye LEE . Skewness of generalized Petersen graphs and related graphs[J]. Frontiers of Mathematics in China, 2012 , 7(3) : 427 -436 . DOI: 10.1007/s11464-012-0186-5

References

Publishing order | Descend order by publishing year | Descend order by cited within
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

DOI

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

DOI

Options
Outlines

/

〈 〉