Km□Pn的交叉数
The Crossing Number of Km-□Pn
Kleš?等人先后确定了Km-□Pn(4≤ m≤ 6)的交叉数,本文利用构造法确定了Km-2K2(4≤ m≤ 12,m≠10,12)的交叉数.在此基础上,可进一步确定Km-□Pn(4≤ m≤ 9,m≠8)的交叉数.相比而言,我们所采用的方法更具一般性.
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.
图 / 画法 / 交叉数 / 笛卡尔积 {{custom_keyword}} /
graph / drawing / crossing number / Cartesian product {{custom_keyword}} /
[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,m□Pn (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)和省高校科技创新团队支持计划项目
/
〈 | 〉 |