KMS Of Academy of mathematics and systems sciences, CAS
The crossing numbers of generalized Petersen graphs with small order | |
Lin Xiaohui1; Yang Yuansheng1; Zheng Wenping1; Shi Lei1; Lu Weiming2 | |
2009-03-06 | |
Source Publication | DISCRETE APPLIED MATHEMATICS |
ISSN | 0166-218X |
Volume | 157Issue:5Pages:1016-1023 |
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. |
Keyword | Generalized Petersen graph Planar graph Crossing number Embedding |
DOI | 10.1016/j.dam.2008.01.012 |
Language | 英语 |
Funding Project | CNSF[60573022] |
WOS Research Area | Mathematics |
WOS Subject | Mathematics, Applied |
WOS ID | WOS:000264646300014 |
Publisher | ELSEVIER SCIENCE BV |
Citation statistics | |
Document Type | 期刊论文 |
Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/8665 |
Collection | 中国科学院数学与系统科学研究院 |
Corresponding Author | Yang Yuansheng |
Affiliation | 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 |
Recommended Citation GB/T 7714 | Lin Xiaohui,Yang Yuansheng,Zheng Wenping,et al. The crossing numbers of generalized Petersen graphs with small order[J]. DISCRETE APPLIED MATHEMATICS,2009,157(5):1016-1023. |
APA | Lin Xiaohui,Yang Yuansheng,Zheng Wenping,Shi Lei,&Lu Weiming.(2009).The crossing numbers of generalized Petersen graphs with small order.DISCRETE APPLIED MATHEMATICS,157(5),1016-1023. |
MLA | Lin Xiaohui,et al."The crossing numbers of generalized Petersen graphs with small order".DISCRETE APPLIED MATHEMATICS 157.5(2009):1016-1023. |
Files in This Item: | ||||||
There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment