点击次数：

论文类型：期刊论文

发表时间：2009-03-06

发表刊物：DISCRETE APPLIED MATHEMATICS

收录刊物：SCIE、EI、Scopus

卷号：157

期号：5

页面范围：1016-1023

ISSN号：0166-218X

关键字：Generalized Petersen graph; Planar graph; Crossing number; Embedding

摘要：The generalized Petersen graph P(n, k) is an undirected graph on 2n vertices with V (P(n, k)) = {a(i), b(i) : 0 <= i <= n - 1} and E(P(n, k)) = {a(i)b(i), a(i)a(i+1), b(i)b(i+k) : 0 <= i <= n - 1, subscripts modulo n}. Fiorini claimed to have determined the crossing numbers of P(n, 3) and showed all the values of cr(P(n, k)) for n up to 14, except 12 unknown values. Lovrecic Sarazin proved cr(P(10, 4)) = cr(P(10, 6)) = 4. Richter and Salazar found a gap in Fiorini's paper, which invalidated his principal results about cr(P(n, 3)), and gave the correct proof for cr(P(n, 3)). In this paper, we show the crossing numbers of all P(n, k) for n up to 16. (C) 2008 Elsevier B.V. All rights reserved.