计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2014年
18期
79-84,108
,共7页
岳为君%黄元秋%欧阳章东
嶽為君%黃元鞦%歐暘章東
악위군%황원추%구양장동
画法%交叉数%联图%圈
畫法%交扠數%聯圖%圈
화법%교차수%련도%권
drawing%crossing number%join graph%Cn
联图G+H 表示将G中每个点与H 中的每个点连边得到的图。在Klesc M.给出联图W3+Cn的交叉数的基础上,应用反证法和排除法得到了联图W4+Cn的交叉数为Z(5,n)+n+ê?ú?n2+4(n3),并在Zarankiewicz猜想成立的前提下,根据证明,提出对Wm+Cn的交叉数的一个猜想:cr(Wm+Cn)=Z(m+1,n)+ê?ú?m2ê?ú?m-12ê?ú?n2+éêùúm2+éêùún2+2,n3。其中Z (m,n)=ê?ú?m2ê?ú?m-12ê?ú?n2ê?ú?n-12,m,n为非负整数。
聯圖G+H 錶示將G中每箇點與H 中的每箇點連邊得到的圖。在Klesc M.給齣聯圖W3+Cn的交扠數的基礎上,應用反證法和排除法得到瞭聯圖W4+Cn的交扠數為Z(5,n)+n+ê?ú?n2+4(n3),併在Zarankiewicz猜想成立的前提下,根據證明,提齣對Wm+Cn的交扠數的一箇猜想:cr(Wm+Cn)=Z(m+1,n)+ê?ú?m2ê?ú?m-12ê?ú?n2+éêùúm2+éêùún2+2,n3。其中Z (m,n)=ê?ú?m2ê?ú?m-12ê?ú?n2ê?ú?n-12,m,n為非負整數。
련도G+H 표시장G중매개점여H 중적매개점련변득도적도。재Klesc M.급출련도W3+Cn적교차수적기출상,응용반증법화배제법득도료련도W4+Cn적교차수위Z(5,n)+n+ê?ú?n2+4(n3),병재Zarankiewicz시상성립적전제하,근거증명,제출대Wm+Cn적교차수적일개시상:cr(Wm+Cn)=Z(m+1,n)+ê?ú?m2ê?ú?m-12ê?ú?n2+éêùúm2+éêùún2+2,n3。기중Z (m,n)=ê?ú?m2ê?ú?m-12ê?ú?n2ê?ú?n-12,m,n위비부정수。
By connecting each vertex of a graph G to each vertex of a graph H , a join graph, denoted by G+H , is obtained. In this paper, based on the crossing number of W3+Cn obtained by Klesc M., it gets that the crossing number of W4+Cn is Z(5,n)+n+ê? ú?n2 +4(n3) by reduction to absurdity and elimination method, and gives a conjecture of the crossing number of Wm+Cn within the conjecture of Zarankiewicz, cr(Wm+Cn)=Z(m+1,n)+ê? ú?m2 ê? ú?m-12 ê? ú?n2 +éê ùúm2 +éê ùún2 +2,n3 , in which Z (m,n)=ê? ú?m2 ê? ú?m-12 ê? ú?n2 ê? ú?n-12 ,m,n is nonnegative integer.