|
|
Skewness of generalized Petersen graphs and related graphs |
Gek Ling CHIA(), Chan Lye LEE |
Institute of Mathematical Sciences, University of Malaya, 50603 Kuala Lumpur, Malaysia |
|
|
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
|
Corresponding Author(s):
CHIA Gek Ling,Email:glchia@um.edu.my
|
Issue Date: 01 June 2012
|
|
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: 10.1007/978-3-540-30540-8_8
|
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: 10.1016/j.disc.2004.07.036
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|