The crossing numbers of generalized Petersen graphs with small order

被引：7

作者：

Lin Xiaohui ^{[1
]}

Yang Yuansheng ^{[1
]}

Zheng Wenping ^{[1
]}

Shi Lei ^{[1
]}

Lu Weiming ^{[2
]}

机构：

[1] Dalian Univ Technol, Dept Comp Sci, Dalian 116024, Peoples R China

[2] Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2009年 / 157卷 / 05期

关键词：

Generalized Petersen graph; Planar graph; Crossing number; Embedding;

D O I：

10.1016/j.dam.2008.01.012

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：1016 / 1023

页数：8

共 9 条

[1] THE CROSSING NUMBERS OF SOME GENERALIZED PETERSEN GRAPHS
EXOO, G
HARARY, F
KABELL, J
[J]. MATHEMATICA SCANDINAVICA, 1981, 48 (02) : 184 - 188
[2] Fiorini S., 1986, ANN DISCRETE MATH, V30, P225
[3] Fiorini S., 2003, Math. Bohem, V128, P337
[4] CROSSING NUMBER IS NP-COMPLETE
GAREY, MR
JOHNSON, DS
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (03): : 312 - 316
[5] 98ON MOBIUS LADDERS
GUY, RK
HARARY, F
[J]. CANADIAN MATHEMATICAL BULLETIN, 1967, 10 (04): : 493 - &
[6] ON THE CROSSING NUMBERS OF CERTAIN GENERALIZED PETERSEN GRAPHS
MCQUILLAN, D
RICHTER, RB
[J]. DISCRETE MATHEMATICS, 1992, 104 (03) : 311 - 320
[7] The crossing number of P(N,3)
Richter, RB
Salazar, G
[J]. GRAPHS AND COMBINATORICS, 2002, 18 (02) : 381 - 394
[8] Sarazin M.L., 1997, Math. Slovaca, V47, P189
[9] Watkins M., 1969, J. Comb. Theory, V6, P152, DOI [10.1016/S0021-9800(69)80116-X, DOI 10.1016/S0021-9800(69)80116-X]

← 1 →