期刊文献+

S_m∨P_n与S_m∨C_n的交叉数 被引量:10

The Crossing Numbers of S_m∨P_n and S_m∨C_n
原文传递
导出
摘要 本文研究与星图有关的联图的交叉数,得到了对任意的n≥1,当m=3,4,5时,星Sm与路P_n的联图的交叉数;以及对任意的n≥3,当m=3,4时,星S_m与圈C_n的联图的交叉数. This paper studies the crossing numbers of the join graphs, and gets the exact value of cr(Sm ∨ Pn) for m = 3, 4, 5 and arbitrary n ≥ 1, and the exact value of cr(Sm ∨ Cn) for m = 3, 4 and arbitrary n ≥ 3.
作者 王晶 黄元秋
出处 《数学进展》 CSCD 北大核心 2011年第5期631-636,共6页 Advances in Mathematics(China)
基金 国家自然科学基金(No.10771062) 新世纪优秀人才支持计划(No.07-0276) 湖南省教育厅项目(No.10C0410) 长沙学院人才引进项目(No.SF0904 No.SF0905) 湖南省研究生科研创新项目(No.CX2009B098) 长沙市科技计划(No.K0902210-11)
关键词 画法 交叉数 联图 graph drawing crossing number join graph
  • 引文网络
  • 相关文献

参考文献19

  • 1Bondy, J.A., Murty, U.S.R., Graph Theory With Application, London, 1976.
  • 2Turan, P., A note of welcome, J. Graph Theory, 1977, 1: 7-9.
  • 3Garey, M.R., Johnson, D.S., Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods, 1983, 4: 312-316.
  • 4Kleitman, D.J., The crossing number of K5,n, J. Combinatorics Theory, 1971, 9: 315-323.
  • 5Klesc, M., On the crossing number of Cartesian products of stars anti paths or cycles, J. Math. Slovaca, 1991, 41: 113-120.
  • 6Klesc, M., The crossing numbers of products of paths and stars with 4*vertex graphs, J. Graph Theory, 1994, 18: 605-614.
  • 7Klesc, M., The crossing number of certain Cartesian products, Discuss. Math-Graph Theory, 1995, 15: 5-10.
  • 8Klesc, M., The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Mathematics, 2001, 233: 353-359.
  • 9Beineke, L.W., Ringeisen, R.D., On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory, 1980, 4: 145-155.
  • 10Wang Jing, Huang Yuanqiu, The crossing number of K2,4* Pn, Acta Mathematica Scientia(in Chinese), 5008, 28A: 251-255.

同被引文献67

  • 1Bondy J A, Murty U S R. Graph theory with application. New York: Elsevier, 1976.
  • 2Garey M R, Johnson D S. Crossing number is NP-complete. SIAM ,I. Algebraic Dis- crete Methods, 4(3)(1983): 312-316.
  • 3Kleitman D J. The crosing number of Ks,n. J.Graph Series B, 9(1970): 315-323.
  • 4Huang Y Q, Zhao T L. The crossing number of K1,4,n. Disc.Math, 308(9)(2008): 1634- 1638.
  • 5Mei Hanfei, Huang Yuanqiu. The crossing number of Kl,5,n. International Journal of Mathematical combinatorics, 1(2007): 33-44.
  • 6Klesc M. The join of graphs and crossing numbers. Electronic Notes in Discrete Math, 28(2007): 349-355.
  • 7Klesc, M. The crossing numbers of join of the special graph on six vertices with path and cycle. Discrete Mathematics, 310(2010): 1475-1481.
  • 8Klesc M. The crossing numbers of join products of path with gaphs of order four Discussiones Mathematicae Graph Theory, 31(2011): 321-331.
  • 9Bondy J A, Murty U S R. Graph theory with application[M]. New York: Macmillan London and Elsevier, 1979.
  • 10Garey M R, Johnson D S. Crossing number is NP-complete[J]. SIAM J Alg Disc Meth, 1983, 4(3): 312-316.

引证文献10

二级引证文献11

;
使用帮助 返回顶部