On the crossing numbers of join of the special graph on six vertices with nK_1, P_n or C_n

Expand
  • 2. College of Mathematics and Statistics, Hengyang Normal University, Hengyang 421002, Hunan, China

Received date: 2016-02-29

  Online published: 2016-12-15

Abstract

The crossing numbers of a graph is a vital parameter and a hard problem in the forefront of topological graph theory.  Determining the crossing number of an arbitrary graphs is NP-complete problem. Because of its difficultly, the classes of graphs whose crossing number have been determined are very scarce. In this paper, for the special graph Q on six vertices, we through the disk drawing method to prove that the crossing numbers of its join with n isolated vertices as well as with the path P_{n} and with the cycle C_{n} are cr(Q+nK_{1})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor, cr(Q+P_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+1 and cr(Q+C_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+3, respectively.

Cite this article

ZHOU Zhidong, LI Long . On the crossing numbers of join of the special graph on six vertices with nK_1, P_n or C_n[J]. Operations Research Transactions, 2016 , 20(4) : 115 -126 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.04.014

References

[1] Kle\v{s}\v{c} M. The join of graphs and crossing numbers [J]. Electronic Notes in Discrete  Mathematics, 2007, 28: 349-355.
[2] Tang L, Wang J, Huang Y Q. The crossing number of the join of C_{n} and P_{n} [J]. International Journal of Mathematical Combinatorics, 2007, 11: 110-116.
[3] Bondy J A,  Murty U S R. Graph Theory with Applications} [M]. {Great Britain: The Macmillan Press Ltd, 1976, 135.
[4] Garey M R, Johnson D S. Crossing number is NP-complete [J]. SIAM Journal on Algebraic Discrete Methods, 1993, 4: 312-316.
[5] Woodall D R. Cyclic-order graphs an Zarankiewicz's crossing number conjecture [J]. Journal of Graph Theory, 1993, 17(6): 657-671.
[6] 苏振华, 黄元秋. 五阶图与路 P_{n} 的联图的交叉数 [J]. 高校应用数学学报, 2014, 29(2): 245-252.
[7] 李敏. 一个 5 阶图与点, 路, 圈联图的交叉数 [J]. 扬州大学学报 (自然科学版}), 2015, 18(1): 4-8.
[8] 李丽萍. 一个五阶图与路, 圈的联图的交叉数 [J]. 数学的实践与认识, 2014, 44(11): 203-211.
[9] 周志东, 黄元秋等.  一个小图与路和圈的联图的交叉数 [J]. 系统科学与数学, 2013, 33(2): 206-216.
[10] Kle\v{s}\v{c} M. The crossing numbers of join of the special graph on six vertices with path and cycle [J]. Discrete Mathematics, 2010, 310: 1475-1481.
[11] 周志东, 吕胜详.  关于一个特殊六阶图与路和圈的联图的交叉数 [J]. 数学进展, 2014, 43(1): 69-80.
Outlines

/