Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (9): 57-61.DOI: 10.3778/j.issn.1002-8331.1702-0005
Previous Articles Next Articles
SU Zhenhua
Online:
Published:
苏振华
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
摘要: 联图[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]。
关键词: 交叉数, 联图, 完全多部图, 圈图
SU Zhenhua. Crossing numbers of join products of K1,1,3∨Cn[J]. Computer Engineering and Applications, 2018, 54(9): 57-61.
苏振华. 联图[K1,1,3∨Cn]的交叉数[J]. 计算机工程与应用, 2018, 54(9): 57-61.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.1702-0005
http://cea.ceaj.org/EN/Y2018/V54/I9/57