On the crossing numbers of K2,3 V C n
-
摘要: 将完全二部图K_2,3的每个顶点与Cn每个点相连, 得到的图记为K_2,3 V Cn. 利用一些完全多部图的交叉数结论, 将K_2,3 V Cn与K_2,3,n比较, 证明了K_2,3 V Cn的交叉数为Z(5, n)+n+3.Abstract: By connecting the vertices of K_2,3$ to the vertices of Cn, a join graph denoted by K_2,3 V Cn was obtained. By utilizing some results of the crossing number of complete multipartite graphs and comparing K_2,3 V Cn to K_2,3,n, we proved that the crossing number of K_2,3 V Cn is Z(5, n)+n+3.
-
Key words:
- join graph /
- drawing /
- crossing number
-
[1] {1}BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York: Macmilan Ltd Press, 1976.{2}GAREY M R, Johnson D J. Crossing number is NP-complete [J]. Slam J Alg Disc Methods, 1983(4): 312-316.{3}KLEITMAN D J. The crossing number of $K_{5, n}$[J]. J Combin Theory, 1971, 9: 315-323.{4}WOODALL D R. Cyclic-order graphs and Zarankiewicz's crossing number conjecture[J]. J Graph Theory, 1993, 17(6): 657-671.{5}OPOROWSKI B, ZHAO D. Coloring graphs with crossings[J]. Discrete Mathematics, doi;10,1016/j.disc, 2008.07.040.{6}TANG L, WANG J, HUANG Y Q. The crossing number of the join of $C_{n}$ and $P_{n}$[J]. International J Math Com, 2007(11): 110-116.{7}PAK Tung Ho. On the crossing number of some complete multipartite graph [J]. Utilitas Mathematica, 2009, 79: 154-143.{8}PAK Tung Ho. The crossing number of $K_{2,2,2,n}$ [J]. Far East Journal of Applied Mathematics, 2008, 30(1): 43-69.{9}ASANO K. The crossing number of $K_{1, 3, n}$ and $K_{2, 3, n}$[J]. J Graph Theory, 1986(10): 1-8.
点击查看大图
计量
- 文章访问数: 2068
- HTML全文浏览量: 16
- PDF下载量: 369
- 被引次数: 0