The crossing numbers of generalized Petersen graphs with small order
文献类型:期刊论文
作者 | Lin Xiaohui1; Yang Yuansheng1; Zheng Wenping1; Shi Lei1; Lu Weiming2 |
刊名 | DISCRETE APPLIED MATHEMATICS
![]() |
出版日期 | 2009-03-06 |
卷号 | 157期号:5页码:1016-1023 |
关键词 | Generalized Petersen graph Planar graph Crossing number Embedding |
ISSN号 | 0166-218X |
DOI | 10.1016/j.dam.2008.01.012 |
英文摘要 | 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. |
资助项目 | CNSF[60573022] |
WOS研究方向 | Mathematics |
语种 | 英语 |
WOS记录号 | WOS:000264646300014 |
出版者 | ELSEVIER SCIENCE BV |
源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/8664] ![]() |
专题 | 中国科学院数学与系统科学研究院 |
通讯作者 | Yang Yuansheng |
作者单位 | 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 |
推荐引用方式 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. |
入库方式: OAI收割
来源:数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。