周志東,李龍

(衡陽師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院,湖南 衡陽,421002)

?

一類聯(lián)圖的交叉數(shù)

周志東,李龍

(衡陽師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院,湖南 衡陽,421002)

聯(lián)圖; 交叉數(shù); 圓盤畫法

性質(zhì)1 令D是圖G的一個好畫法,且A，B，C是圖G的三個互不相交的邊子集,則有

(1)crD(A∪B)=crD(A)+crD(B)+crD(A,B)

(2)crD(A∪B,C)=crD(A,C)+crD(B,C)

性質(zhì)3[2]設(shè)φ是Q+Cn的一個最優(yōu)畫法，則crφ(E(Cn))=0。

把圖G在好畫法D下的每一個交叉點看成一個新的頂點，則得到平面圖G*和對應(yīng)平面嵌入D*，我們把平面圖G*在D*下的面稱為圖G在畫法D下的域。

Jordan曲線定理[3]設(shè)J是平面上的一條Jordan曲線，平面的剩余部分被分成兩個不相交的開集，稱為J的內(nèi)部和外部,分別記為intJ和extJ并且用IntJ和ExtJ表示它們的閉包。顯然IntJ∩ExtJ=J，則連接intJ的點和extJ的點的任何連線必在某點和J相交，其中一條Jordan曲線是指一條連續(xù)的、自身不相交的、起點和終點相重合的曲線。

令G1和G2是兩個點不相交的圖，圖G1和G2的聯(lián)圖G1+G2是這樣的一個圖:頂點集

V(G1+G2)=V(G1)∪V(G2)，邊集E(G1+G2)=E(G1)∪E(G2)∪{e(u,v)|u∈V(G1)，且|v∈V(G2)}。其中，e(u,v)表示連接頂點u和v的邊。

圖的交叉數(shù)是圖的一個重要參數(shù),在VLSI布局，離散幾何，數(shù)論，生物工程等領(lǐng)域都有廣泛的應(yīng)用。Garey和Johnson[4]證明確定圖的交叉數(shù)是NP-難問題。目前，確定圖類的交叉數(shù)主要集中在一些具有特殊結(jié)構(gòu)的圖類上，如，完全2-部圖，完全3-部圖，簡單的圖之間的笛卡爾積圖，循環(huán)圖以及Petersen圖等。特別地，關(guān)于完全2-部圖Km,n,Kleitman[5]證明了

記上式右邊表達式為Z(m,n)(這里，對任意實數(shù)x,?x」表示不超過x的最大整數(shù))。

M.Klesc在文獻[1]中確定了路Pm，圈Cm以及階數(shù)不超過4的簡單圖與路,圈的聯(lián)圖的交叉數(shù),在文獻[6]中確定了一個6階圖Q與n個孤立點，路Pn以及圈Cn的聯(lián)圖的交叉數(shù)。本文通過圓盤畫法這一新途徑，確定了另一個6階圖Q(見圖1)與n個孤立點，路Pn以及圈Cn的聯(lián)圖的交叉數(shù)。

圖1 6點圖Q

圖2 Q+nK1的一個好畫法

1 引理

首先，證明幾個引理。

圖3 Q+K1的一個好畫法

證明 當n=1時，如圖3,Q+K1包含一個K3,3的子圖{c,e,f;a,d,t1}，因此cr(Q+K1)=1。

而crφ(T1∪T2,Ti)≥cr(K3,6)=Z(6,3)=6，

crφ(Q∪T1∪T2)≥crφ(Q+2K1)=3，因此，

crφ(Q+nK1)≥3+6(n-2)+Z(6,n-2)+

圖Q的圓盤畫法:設(shè)D是一個圓盤,φ是Q的一個好畫法,使得Q的所有點位于D邊界,Q的所有邊位于D的內(nèi)部,則稱φ為Q的一個圓盤D畫法.在畫法φ下,D的區(qū)域分成如下兩種類型:

α-型區(qū)域:區(qū)域邊界全部由Q的邊弧組成。

β-型區(qū)域:區(qū)域邊界由Q的邊弧及圓盤邊界弧組成。

注意:β-型區(qū)域的邊界只含一段圓盤邊界弧(否則Q不連通)。

引理4 設(shè)D是一個圓盤,φ是6點圖Q的一個圓盤D好畫法,則

(1)圓盤D的β-型區(qū)域邊界最多含有Q的2個頂點,

(2)圓盤D的α-型區(qū)域邊界最多含有Q的3個頂點.因此,有6個β-型區(qū)域。

證明 先證結(jié)論(1):反設(shè)β-型區(qū)域邊界含有Q的頂點個數(shù)不小于3，由于β-型區(qū)域只含一段圓盤邊界弧，則此時Q中必存在割點,與Q本身無割點矛盾?，F(xiàn)分如下情形來證明結(jié)論(2):情形(1):若α-型區(qū)域邊界含有Q的6個頂點的區(qū)域,易知Q中每一個點的度不大于2,矛盾。

情形(2):若α-型區(qū)域邊界含有Q的5個頂點的區(qū)域,如圖4所示，不妨設(shè)Q的另一個頂點x位于圓盤邊界弧x1x5之間,則x只能與x1,x5相連,易導(dǎo)出dQ(xi)≤2(i=2,3,4)；dQ(xi)≤3(i=1,5) ，dQ(x)≤2，這與Q中有4度點矛盾。

情形(3):若α-型區(qū)域邊界含有Q的4個頂點的區(qū)域,如圖5所示,則圓盤邊界被分成4段弧x1x2，x2x3，x3x4，x4x1,則Q的另外兩個點s和t；或者位于相鄰弧段上,或者位于間隔弧段上,或者同時位于同一弧段上。

圖4 含有Q的5個頂點的區(qū)域

圖5 含有Q的4個頂點的區(qū)域

(1)若s和t位于同一弧段上,不妨設(shè)s和t位于同一弧段x1x2上。

由于Q中點的度為2或3或4,而s和t只能與x1,x2相連,易知點x3,x4的度dQ(x3)=dQ(x4)=2，這與Q中只有一個2度點相矛盾。

(2)若s和t位于相間隔弧段上,不妨設(shè)s位于弧段x1x2上;t位于弧段x3x4上,則s只能與x1,x2相連，t只能與x3,x4相連,易知dQ(s)≤2，dQ(t)≤2 ，dQ(xi)≤3(i=1,2,3,4) 這與Q中有4度點矛盾。

(3)若s和t位于相鄰的弧段上,不妨設(shè)s位于弧段x1x2上，t位于弧段x1x4上，則s只能與x1,x2相連,t只能與x1,x4相連,則易dQ(x3)≤2,dQ(s)≤2dQ(t)≤2；這與Q中只有一個點的度不超過2相矛盾。綜上所述,引理4得證。

2 定理的證明

由引理1,只要考慮n≥3，反設(shè)存在Q的好畫法φ使得

(1)

由引理2和3,可假定

圖6 Q∪T1的限制畫法

(1)若點ti落入α-型區(qū)域，由圓盤畫法知此時α-型區(qū)域最多只含有Q的3個頂點且滿足crφ(Ti,Tj)≥1，因此crφ(Q∪T1,Ti)≥4，且此時crφ(Q,Ti)≥3。

(2)若點ti落入β-型區(qū)域和任意細分的子區(qū)域ri(i=1,2,...,6),由于這類區(qū)域只含有Q的2個頂點,又crφ(Ti,Tj)≥1且這些區(qū)域之間至少有兩個不相鄰,由Jordan曲線定理有crφ(Q∪T1,Ti)≥6.設(shè)有s個ti落入α-型區(qū)域,則有n-1-s落入β-型區(qū)域和任意細分的子區(qū)域ri(i=1,2,...,6),因此

6(n-1-x)+4x+1+Z(6,n-1)=

Z(6,n-1)+6(n-1)-2x+1

(2)

由假設(shè)(1)有

2|A1|+3|A2|+|A3|≤crφ(Q,Ti)≤n+

(3)

顯然,|A1|+|A2|+|A3|=n-1

(4)

由(3)(4)式可得

(5)

則有

代入(6)式有

與(1) 矛盾,從而定理證畢。

斷言:在畫法φ下Pn自身不相交,且crφ(Q,Pn)=0。

情形(1):區(qū)域α最多含有Q中的4個點。則對?1≤i≤n,有crφ(Q,Ti)≥2。因此

情形(2):區(qū)域α恰好含有Q中的5個點。此時,對?1≤i≤n,有crφ(Q,Ti)≥1，又分如下兩種子情形:

圖7 區(qū)域α恰含有5個點的情形

圖8 區(qū)域α恰含有6個點的情形

情形(3):區(qū)域α恰含有Q中的6個頂點。

子情形(3.1):若存在一點,設(shè)為t1,使得crφ(Q,T1)=0。如圖8所示:α-細分為α1,α2,α3,α4,α5,α66個區(qū)域。由Pn上無交叉點,不妨設(shè)Pn的其余所有點ti(i≥2)位于α1區(qū)域,對?2≤i≤n,由于至少有2個領(lǐng)域不相鄰,由Jordan曲線定理crφ(Q∪T1,Ti)≥5,且此時Q自身有1個交叉。則有

在這種情況下,crφ(Q∪T1,Ti)=4,進一步有crφ(Q,Ti)≥2，因此

(注意到n≥3)，矛盾。

(8)

斷言1 圖Cn自身不交叉。由性質(zhì)3即得。

斷言2 圖Cn最多只有2個交叉。由假設(shè)即得。

情形1:crφ(Cn,Q)=0。不妨設(shè)Q的所有點和邊都位于Cn的內(nèi)部。

情形2:Cn與Q有相交,即crφ(Q,Cn)≠0。

由于Cn與Q都是2-連通的,因此crφ(Q,Cn)≥2,若crφ(Q,Cn)≥3，即Cn上至少有3個交叉。因此只需考慮crφ(Q,Cn)=2的情形,分如下子情形:

子情形2.2:Q中有點位于Cn的內(nèi)部區(qū)域,也有點位于Cn的外部區(qū)域.

設(shè)與Cn發(fā)生交叉的這兩條邊為e1和e2,由此可知{e1,e2}為Q的割邊集,由圖Q可知,這個割邊集只可能是與Q中某個2-度點關(guān)聯(lián)的2條邊,不妨設(shè)這個2-度點位于Cn的外部區(qū)域,則Q的其它所有點必須位于Cn的內(nèi)部區(qū)域,否則由Q是連通圖,2度點x0與Q中任意點有路相連,這導(dǎo)致Cn上至少有3個交叉。則Q中的5個點(除x0外)均與圈Cn上的n個點相連,且這些邊均畫在Cn圍成的內(nèi)部區(qū)域。由性質(zhì)2有

[1]Klesc 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 Cnand Pn[J].International Journal 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.

[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]Klesc M.The crossing numbers of join of the special graph on six vertices with path and cycle[J].Discrete Mathematics,2010,310:1475-1481.

Onthecrossingnumberofthejointgraph

ZHOU Zhidong,LI Long

(Department of Mathematics and Computational Science,Hengyang Normal University，Hengyang 421002，China)

jointgraph；crossingnumber;diskcompassdrawing

1672-7010(2016)03-0016-09

2016-03-20

國家自然科學(xué)基金資助項目(11401185)；湖南省自然科學(xué)基金項目(14JJ6039)；湖南省“十三五”重點建設(shè)學(xué)科項目資助；衡陽師范學(xué)院科學(xué)啟動基金(13B39)

周志東(1980—)，男，湖南邵陽人,博士，從事圖論及其應(yīng)用研究；E-mail:zzdongwww@163.com

O

A