CSpace
The crossing numbers of generalized Petersen graphs with small order
Lin Xiaohui1; Yang Yuansheng1; Zheng Wenping1; Shi Lei1; Lu Weiming2
2009-03-06
Source PublicationDISCRETE APPLIED MATHEMATICS
ISSN0166-218X
Volume157Issue:5Pages:1016-1023
AbstractThe 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.
KeywordGeneralized Petersen graph Planar graph Crossing number Embedding
DOI10.1016/j.dam.2008.01.012
Language英语
Funding ProjectCNSF[60573022]
WOS Research AreaMathematics
WOS SubjectMathematics, Applied
WOS IDWOS:000264646300014
PublisherELSEVIER SCIENCE BV
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/8665
Collection中国科学院数学与系统科学研究院
Corresponding AuthorYang Yuansheng
Affiliation1.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.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Lin Xiaohui]'s Articles
[Yang Yuansheng]'s Articles
[Zheng Wenping]'s Articles
Baidu academic
Similar articles in Baidu academic
[Lin Xiaohui]'s Articles
[Yang Yuansheng]'s Articles
[Zheng Wenping]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Lin Xiaohui]'s Articles
[Yang Yuansheng]'s Articles
[Zheng Wenping]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.