KmPn的交叉数

欧阳章东, 黄元秋

数学学报 ›› 2016, Vol. 59 ›› Issue (3) : 405-410.

PDF(431 KB)
PDF(431 KB)
数学学报 ›› 2016, Vol. 59 ›› Issue (3) : 405-410. DOI: 10.12386/A2016sxxb0039
论文

KmPn的交叉数

    欧阳章东1, 黄元秋2
作者信息 +

The Crossing Number of Km-Pn

    Zhang Dong OUYANG1, Yuan Qiu HUANG2
Author information +
文章历史 +

摘要

Kleš?等人先后确定了Km-Pn(4≤ m≤ 6)的交叉数,本文利用构造法确定了Km-2K2(4≤ m≤ 12,m≠10,12)的交叉数.在此基础上,可进一步确定Km-Pn(4≤ m≤ 9,m≠8)的交叉数.相比而言,我们所采用的方法更具一般性.

Abstract

The crossing numbers of Km-Pn were successively determined for 4 ≤ m ≤ 6 by Kleš? et al.In this paper,the crossing numbers of Km--2K2 are obtained by the construction method for 4 ≤ m ≤ 12 and m≠10,12.On the basis,the crossing numbers of Km-Pn for 4 ≤ m ≤ 9 and m≠8 can be determined.The method that we use is more general relatively.

关键词

/ 画法 / 交叉数 / 笛卡尔积

Key words

graph / drawing / crossing number / Cartesian product

引用本文

导出引用
欧阳章东, 黄元秋. KmPn的交叉数. 数学学报, 2016, 59(3): 405-410 https://doi.org/10.12386/A2016sxxb0039
Zhang Dong OUYANG, Yuan Qiu HUANG. The Crossing Number of Km-Pn. Acta Mathematica Sinica, Chinese Series, 2016, 59(3): 405-410 https://doi.org/10.12386/A2016sxxb0039

参考文献

[1] Bondy J. A., Murty U. S. R., Graph Theory with Applications, Macmillan Press Ltd, London, 1976.
[2] Bokal D., On the crossing number of Cartesian products with paths, J. Combin. Theory Series B, 2007, 97:381-384.
[3] Erdös P., Guy R. K., Crossing number problems, Amer. Math. Mon., 1973, 80:52-58.
[4] Garey M. R., Johnson D. S., Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods, 1983, 4:312-316.
[5] Kleš? M., The crossing numbers of products of paths and stars with 4-vertex graphs, J. Graph. Theory, 1994, 18:605-614.
[6] Kleš? M., The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Math., 2001, 233:353-359.
[7] Ouyang Z. D., Wang J., Huang Y. Q., On the crossing number of K1,1,mPn (in Chinese), Scientia Sinica Math., 2014, 44(12):1337-1342.
[8] Ouyang Z. D., Wang J., Huang Y. Q., The crossing number of Cartesian product of paths with complete graphs, Discrete Math., 2014, 328:71-78.
[9] Yang X. W., The Crossing Number of Flower Snark and Km-Pn (in Chinese), Master Thesis, Dalian University of Technology, Dalian, 2007.

基金

国家自然科学基金资助项目(11301169,11371133);湖南省自然科学基金资助项目(13JJ4110);湖南省优秀博士学位论文获得者资助项目(YB2013B040)和省高校科技创新团队支持计划项目

PDF(431 KB)

Accesses

Citation

Detail

段落导航
相关文章

/