计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (9): 57-61.DOI: 10.3778/j.issn.1002-8331.1702-0005

• 理论与研发 • 上一篇    下一篇

联图[K1,1,3∨Cn]的交叉数

苏振华   

  1. 怀化学院 数学系,湖南 怀化 418008
  • 出版日期:2018-05-01 发布日期:2018-05-15

Crossing numbers of join products of K1,1,3∨Cn

SU Zhenhua   

  1. Department of Mathematics, Huaihua University, Huaihua, Hunan 418008, China
  • Online:2018-05-01 Published:2018-05-15

摘要: 联图[G∨H]表示将[G]的每个顶点与[H]的每个顶点连边得到的图。在Klesc给出的联图[K1,1,2∨Cn]的交叉数为[Z(4,n)+n2+3]的基础上,根据联图的相关性质,运用反证法和排除法,得到了联图[K1,1,3∨Cn]与[{K1,1,3+e}∨Cn]的交叉数均为[Z(5,n)+n+n2+4]。并假设在Zarankiewicz猜想成立的前提下,提出对[K1,1,m∨Cn(m≥4)]的交叉数的一个猜想:[cr?(K1,1,m∨Cn)≥Z(m+2,n)+m+12m2n2+m2m-12n2+][m+1,m≥4]。

关键词: 交叉数, 联图, 完全多部图, 圈图

Abstract: A join graph denoteted by[G∨H], is illustrated by connecting each vertex of graph[G]to each vertex of graph[H]. Based on the result that the crossing numbers of [K1,1,2∨Cn] is [Z(4,n)+n2+3] obtained by Klesc, obtain that the crossing numbers of join products[K1,1,3∨Cn]as well as[{K1,1,3+e}∨Cn]are[Z(5,n)+n+n2+4]. The proofs depend on the properties about the join products, and using reduction to absurdity and elimination method. Moreover, a conjecture is given on the crossing number of[K1,1,m∨Cn(m≥4)] within the conjecture of Zarankiewicz:[cr?(K1,1,m∨Cn)≥Z(m+2,n)+][m+12m2n2+m2m-12n2][+m+1,m≥4.]

Key words: crossing numbers, join products, complete multipartite graph, cycle