The crossing numbers of generalized Petersen graphs with small order

doi:10.1016/j.dam.2008.01.012

CSpace

	The crossing numbers of generalized Petersen graphs with small order
	Lin Xiaohui 1; Yang Yuansheng 1; Zheng Wenping 1; Shi Lei 1; Lu Weiming 2
	2009-03-06
发表期刊	DISCRETE APPLIED MATHEMATICS
ISSN	0166-218X
卷号	157 期号:5 页码:1016-1023
摘要	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.
关键词	Generalized Petersen graph Planar graph Crossing number Embedding
DOI	10.1016/j.dam.2008.01.012
语种	英语
资助项目	CNSF[60573022]
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:000264646300014
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/8665
专题	中国科学院数学与系统科学研究院
通讯作者	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.