Hits:

Indexed by:期刊论文

Date of Publication:2009-03-06

Journal:DISCRETE APPLIED MATHEMATICS

Included Journals:SCIE、EI、Scopus

Volume:157

Issue:5

Page Number:1016-1023

ISSN No.:0166-218X

Key Words:Generalized Petersen graph; Planar graph; Crossing number; Embedding

Abstract: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.