限制度的IC平面圖中輕弦4-圈的權(quán)和

田 京 京

(陜西理工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 陜西 漢中 723000)

1 引言與預(yù)備知識(shí)

圖論因其表述能力強(qiáng)和算法高效在大數(shù)據(jù)分析中應(yīng)用廣泛. 圖的結(jié)構(gòu)問題是圖論研究的核心問題之一, 是圖論理論研究及圖染色和標(biāo)號模型[1-3]的基礎(chǔ). Ringel[4]在研究平面圖的點(diǎn)-面染色時(shí)提出了1-平面圖的概念, 之后, Albertson[5]提出了IC-平面圖的概念. 目前平面圖中輕子圖的研究已取得一些成果[6-8]: Kotzig[6]證明了任意3-連通的平面圖包含一條邊, 且與這條邊所關(guān)聯(lián)的兩頂點(diǎn)的度之和至多為13; Fabrici等[9]證明了每個(gè)3-連通的1-平面圖含有一條輕邊且輕邊高度的上界為20, 并證明了最小度至少為6的1-平面圖包含一個(gè)3-圈uvw, 且max{d(u),d(v),d(w)}≤10; Hudk等[10]證明了最小度至少為6的1-平面圖包含一個(gè)4-圈, 且4-圈上點(diǎn)的度至多為47; Zhang等[11]證明了最小度至少為6的1-平面圖包含一個(gè)4-圈, 且4-圈上點(diǎn)的度至多為19, 以及在最小度為7的1-平面圖中含有輕K4且輕K4高度的上界是11； Tian等[12]證明了每個(gè)最小度至少為5的NIC-平面圖含有一個(gè)3-圈uvw, 且max{d(u),d(v),d(w)}≤26; 田京京等[13]證明了每個(gè)最小度至少為5且最小邊度至少為11的IC-平面圖G輕3-圈高度的上界為17; Niu等[14]證明了最小度至少為3的1-平面圖中存在輕邊. 本文利用權(quán)轉(zhuǎn)移的方法討論最小度為5且最小邊度為11的IC-平面圖中含有輕弦4-圈且權(quán)和的上界小于等于37.

定義1[5]圖G稱為1-平面圖, 當(dāng)且僅當(dāng)圖G可畫在一個(gè)平面上, 且每條邊至多被交叉一次. 若G上存在交叉點(diǎn), 則必為G的某兩條邊交叉產(chǎn)生, 于是G中每個(gè)交叉點(diǎn)c都可與G中的4個(gè)頂點(diǎn)(即兩條交叉邊上的4個(gè)頂點(diǎn))所構(gòu)成的點(diǎn)集建立對應(yīng)關(guān)系, 該對應(yīng)關(guān)系記為S. 顯然在一個(gè)好的1-平面圖畫法(即交叉點(diǎn)最少的畫法)中, 對于任意兩個(gè)交叉點(diǎn)c1,c2, 存在|S(c1)∩S(c2)|≤2. 若1-平面圖的兩個(gè)子類滿足|S(c1)∩S(c2)|=0, 則稱該1-平面圖為IC-平面圖.

定義3[11]如果將圖G中的所有交叉點(diǎn)均視為4-度點(diǎn), 則可得一個(gè)交叉數(shù)為0的圖G×, 稱為G的關(guān)聯(lián)圖. 設(shè)v是圖G×中的一個(gè)點(diǎn), 如果v∈V(G×)V(G), 則稱v是G×的一個(gè)假點(diǎn)或稱v是G的一個(gè)交叉點(diǎn), 否則稱v為G×的一個(gè)真點(diǎn). 設(shè)uv是圖G×中的一條邊, 如果uv∈E(G)E(G×), 則稱uv是G×的一條假邊或稱其為G的一條交叉邊, 否則稱uv為G×的一條真邊. 設(shè)f是圖G×的一個(gè)面, 如果f關(guān)聯(lián)至少一個(gè)假點(diǎn), 則稱f為G×的一個(gè)假面, 否則稱f為G×的一個(gè)真面. 由關(guān)聯(lián)圖G×的定義知, 對于G中的每個(gè)點(diǎn)v, 總有dG(v)=dG×(v). 圖G中任意一條邊uv所關(guān)聯(lián)的點(diǎn)u,v度之和d(u)+d(v)稱為邊uv的度.

本文討論的圖類范圍僅限于簡單的有限無向圖, 分別用V(G),E(G),F(G),Δ(G),δ(G)表示G中的點(diǎn)集合、 邊集合、 面集合、 最大度和最小度. 用k-,k+-和k--點(diǎn)或面分別表示一個(gè)點(diǎn)或面的度為k(至少為k和至多為k). 對于G中的一個(gè)點(diǎn)v, 用fk(v)表示v在G×中關(guān)聯(lián)的k-面?zhèn)€數(shù), 用nc(v)表示v在G×中相鄰的假點(diǎn)個(gè)數(shù). 設(shè)v是G×中的k-點(diǎn),v1,v2,…,vk是v在G×中按順時(shí)針排列的所有鄰點(diǎn). 在G×中與邊vvi和vvi+1關(guān)聯(lián)的面記為fi(1≤i≤k), 并記vk+1∶=v1. 其余定義若無特殊說明均參考文獻(xiàn)[15].

2 主要結(jié)果

定理1每個(gè)最小度至少為5且最小邊度至少為11的IC-平面圖含有一個(gè)弦4-圈v1v2v3v4v1, 且d(v1)+d(v2)+d(v3)+d(v4)≤37.

證明： 反證法. 假設(shè)結(jié)論不真, 則存在一個(gè)反例G, 其所包含的任意一個(gè)弦4-圈v1v2v3v4v1都滿足d(v1)+d(v2)+d(v3)+d(v4)≥38. 設(shè)G×是G的關(guān)聯(lián)圖, 給G×中的每個(gè)點(diǎn)v賦初始權(quán)值為c(v)=d(v)-6, 并給G×中的每個(gè)面f賦初始權(quán)值為c(f)=2d(f)-6, 根據(jù)平面圖G×上的Euler公式, 有

按如下規(guī)則對V(G×)∪F(G×)上的所有元素重新分配權(quán)值.

1) 設(shè)f=xyz是G×中的一個(gè)3-面,d(x)=m.

① 若x是7-點(diǎn),z是4-點(diǎn), 則x向z轉(zhuǎn)移3/10； 若x是8-點(diǎn),z是4-點(diǎn), 則x向z轉(zhuǎn)移1; 若x是9-點(diǎn),z是4-點(diǎn), 則x向z轉(zhuǎn)移8/9; 若x是10+-點(diǎn),z是4-點(diǎn), 則x向z轉(zhuǎn)移1.

② 若x是7-點(diǎn),z是5-點(diǎn), 則x向z轉(zhuǎn)移1/10； 若x是8-點(diǎn),z是5-點(diǎn), 則x向z轉(zhuǎn)移1/10; 若x是9-點(diǎn),z是5-點(diǎn), 則x向z轉(zhuǎn)移1/9; 若x是10+-點(diǎn),z是5-點(diǎn), 則x向y轉(zhuǎn)移(m-8)/m.

③ 若f是真3-面且yz關(guān)聯(lián)一個(gè)假3-面f′=yzs, 其中7≤d(x)≤9, 則x通過yz向s轉(zhuǎn)移1/2; 若f是真3-面且yz關(guān)聯(lián)一個(gè)假3-面f′=yzs, 其中x是一個(gè)10+-點(diǎn), 則x通過yz向s轉(zhuǎn)移1/2.

設(shè)f是G×中的一個(gè)4+-面.

①f向其關(guān)聯(lián)的4-點(diǎn)轉(zhuǎn)移1.

②f向其關(guān)聯(lián)的5-點(diǎn)轉(zhuǎn)移1/2.

③ 若f的某條邊xy關(guān)聯(lián)一個(gè)3-面f′=xyz且z是4-點(diǎn), 則f通過xy向z轉(zhuǎn)移1/2.

設(shè)c′(x)為元素x∈V(G×)∪F(G×)在應(yīng)用上述權(quán)轉(zhuǎn)移規(guī)則后得到的新權(quán)值, 下面證明對每個(gè)x∈V(G×)∪F(G×)都有c′(x)≥0. 因此,

矛盾.

首先, 驗(yàn)證對任意的f∈F(G×), 有c′(f)≥0.

若d(f)=3, 則由規(guī)則1),2)知c′(f)=c(f)=0. 若d(f)=4, 則由G的最小邊度至少為11知, 面f最多關(guān)聯(lián)2個(gè)5-點(diǎn). 若面f關(guān)聯(lián)1個(gè)4-點(diǎn), 則由IC-平面圖的定義知, 規(guī)則2)中③不可能再應(yīng)用于面f, 因此, 由規(guī)則2)中①,②可知

另一方面, 若面f不關(guān)聯(lián)4-點(diǎn), 則由IC-平面圖的定義知, 規(guī)則2)中③最多應(yīng)用于面f兩次, 因此, 由規(guī)則2)中①,③可知

若d(f)=5, 則考慮下列兩種情形.

(i) 若面f不關(guān)聯(lián)4-點(diǎn), 則由G的最小邊度至少為11知, 面f最多關(guān)聯(lián)2個(gè)5-點(diǎn). 由IC-平面圖的定義知, 規(guī)則2)中③最多應(yīng)用于面f兩次. 因此, 由規(guī)則2)中②,③可知

(ii) 若面f關(guān)聯(lián)1個(gè)4-點(diǎn), 則由G的最小邊度至少為11知, 面f最多關(guān)聯(lián)2個(gè)5-點(diǎn). 由IC-平面圖的定義知, 規(guī)則2)中③最多應(yīng)用于面f一次. 因此, 由規(guī)則2)中①,②,③可知

其次, 驗(yàn)證對任意的v∈V(G×), 有c′(v)≥0.

根據(jù)規(guī)則1),2)知, 圖G×中的6-點(diǎn)不參與權(quán)轉(zhuǎn)移, 因此d(v)=6, 從而c′(v)=c(v)=d(v)-6≥0. 下面考慮6種情形.

情形1)d(v)=4.

① 若v至少關(guān)聯(lián)2個(gè)4+-面, 則由規(guī)則2)中①得c′(v)≥4-6+1×2=0.

② 若v僅關(guān)聯(lián)1個(gè)4+-面, 不妨設(shè)其為f1, 則f2,f3,f4均為3-面. 假設(shè)v1,v2,v3,v4中不存在1個(gè)10+-點(diǎn), 則v1,v2,v3,v4一定是9--點(diǎn), 于是這4個(gè)點(diǎn)的度之和為36, 與圖G上任意一個(gè)弦4-圈上點(diǎn)的度之和均大于等于38矛盾, 所以v1,v2,v3,v4中存在一個(gè)10+-點(diǎn). 由規(guī)則1)中①知v4向v轉(zhuǎn)1, 由規(guī)則2)中①知f1向v轉(zhuǎn)1, 故c′(v)≥d(v)-6+1×1+1×1=0.

③ 若v僅關(guān)聯(lián)3-面, 即f1,f2,f3,f4均為3-面, 則由G是一個(gè)反例知,G中弦4-圈上4個(gè)點(diǎn)度之和大于等于38, 因此, 可分下列幾種情形討論.

(i) 若觀察v1,v2,v3,v4中任意三點(diǎn), 可發(fā)現(xiàn)這三點(diǎn)至少有2個(gè)6點(diǎn)或2個(gè)7點(diǎn), 且三點(diǎn)的度之和大于等于17, 小于等于21, 于是v1,v2,v3,v4中剩下的那個(gè)點(diǎn)是17+-點(diǎn), 不妨設(shè)為v4. 根據(jù)規(guī)則1)中①可知v4向v轉(zhuǎn)1. 此時(shí)與v2v3關(guān)聯(lián)的另一個(gè)面或者是4+-面, 或者是真3-面f′=v2v3u, 其中u為17+-點(diǎn). 同時(shí),v3v4關(guān)聯(lián)的另一個(gè)面或者是4+-面, 或者是真3-面f′=v3v4w, 其中w為17+-點(diǎn). 因此, 根據(jù)規(guī)則1)中①,③和2)中③可知

(ii) 若v1,v2,v3,v4中任意兩點(diǎn)度之和小于等于18, 剩余兩點(diǎn)為10+-點(diǎn), 則由規(guī)則1)中①得

c′(v)≥d(v)-6+1×2=0.

(iii) 若v1,v2,v3,v4中有3個(gè)8-點(diǎn), 則由規(guī)則1)中①得

(iv) 若v1,v2,v3,v4中有2個(gè)8-點(diǎn)、 1個(gè)7-點(diǎn)、 1個(gè)15+-點(diǎn), 則由規(guī)則1)中①得

(v) 若v1,v2,v3,v4中有2個(gè)8-點(diǎn)、 1個(gè)9-點(diǎn)、 1個(gè)13+-點(diǎn), 則由規(guī)則1)中①得

情形2)d(v)=5.

① 若v至少關(guān)聯(lián)2個(gè)4+-面, 則由規(guī)則2)中②得

② 若v僅關(guān)聯(lián)1個(gè)4+-面, 不妨設(shè)其為f1, 則f2,f3,f4,f5均為3-面. 由G的IC-平面性可知,v1,v2,v3,v4,v5中僅有1個(gè)4-點(diǎn), 設(shè)d(v3)=4. 由最小邊度為11知,v1,v2,v4,v5均是6+-點(diǎn). 由于G是一個(gè)反例, 因此圖G上任意一個(gè)弦4-圈上點(diǎn)的度之和都大于等于38. 因此分為如下幾種情形討論.

(i) 設(shè)d(v2)=6,d(v5)=6,d(v1)=6,d(v4)≥21. 由規(guī)則1)中②知v5向v轉(zhuǎn)移(m-8)/m=13/21, 由規(guī)則2)中②知f1向v轉(zhuǎn)移1/2, 故有

(ii) 設(shè)d(v2)=9,d(v1)=9,d(v5)≥16,d(v4)≥8. 由規(guī)則1)中②知v5向v轉(zhuǎn)移(m-8)/m=1/2, 由規(guī)則2)中②知f1向v轉(zhuǎn)移1/2, 故有

(iii) 設(shè)d(v1)=d(v2)=7,d(v4)=d(v5)=13+. 由規(guī)則1)中②知v5向v轉(zhuǎn)移(m-8)/m=5/13, 由規(guī)則2)中②知f1向v轉(zhuǎn)移1/2, 故有

(iv) 設(shè)d(v1)=d(v2)=8,d(v4)=13+,d(v5)=12. 由規(guī)則1)中②知v5向v轉(zhuǎn)移(m-8)/m=1/3, 由規(guī)則2)中②知f1向v轉(zhuǎn)移1/2, 故有

(v) 設(shè)d(v1)=d(v2)=9,d(v4)=d(v5)=12+. 由規(guī)則1)中②知v5向v轉(zhuǎn)移(m-8)/m=1/3, 由規(guī)則2)中②知f1向v轉(zhuǎn)移1/2, 故有

(vi) 設(shè)d(v1)=d(v2)=10,d(v4)=11,d(v5)=12+. 由規(guī)則1)中②知v5向v轉(zhuǎn)移(m-8)/m=3/11, 由規(guī)則2)中②知f1向v轉(zhuǎn)移1/2, 故有

(vii) 設(shè)d(v1)=d(v2)=11,d(v4)=11,d(v5)=11+. 由規(guī)則1)中②知v轉(zhuǎn)移(m-8)/m=3/11, 由規(guī)則2)中②知f1向v轉(zhuǎn)移1/2, 故有

③ 若v關(guān)聯(lián)的全是3-面, 則由G的IC-平面性可知v1,v2,v3,v4,v5中僅有1個(gè)4-點(diǎn). 設(shè)d(v3)=4, 由最小邊度為11知,v1,v2,v4,v5均是6+-點(diǎn). 由于G是一個(gè)反例, 因此圖G上任意一個(gè)弦4-圈上點(diǎn)的度之和都大于等于38. 因此可分如下幾種情形討論.

(i) 若v1,v2,v3,v5中有2個(gè)16+-點(diǎn), 則根據(jù)規(guī)則1)中②知v5向v分別轉(zhuǎn)移(m-8)/m=1/2, 故

(ii) 若d(v1)=d(v3)=9,d(v2)=15+,d(v5)=15+, 則根據(jù)規(guī)則1)中②知,v2,v5向v轉(zhuǎn)移(m-8)/m=7/15,v1,v3向v轉(zhuǎn)移1/9, 故

(iii) 若d(v1)=d(v3)=10,d(v2)=13+,d(v5)=13+, 則根據(jù)規(guī)則1)中②知,v5向v轉(zhuǎn)移(m-8)/m=5/13,v5向v轉(zhuǎn)移(m-8)/m=1/5, 故

(iv) 若v1,v2,v4,v5均是11+-點(diǎn), 則根據(jù)規(guī)則1)中②知,v1,v2,v4,v5分別向v轉(zhuǎn)移(m-8)/m=3/11, 故

情形3)d(v)=7.

情形4)d(v)=8.

情形5)d(v)=9.

情形6)d(v)≥10.

不妨設(shè)fi1,fi1+1,…,fi1+t1-1,fi2,fi2+1,…,fi2+t2-1,…,fik,fik+1,…,fik+tk-1為與v關(guān)聯(lián)的所有3-面(其在v的周圍按順時(shí)針排列), 其中當(dāng)k≥2時(shí), 對所有的1≤s≤k-1,fis+ts-1與fis+1不相鄰, 且fik+tk-1與fi1也不相鄰, 此時(shí)d=10. 注意到上述下標(biāo)中的加法運(yùn)算是在模d意義下進(jìn)行的, 且當(dāng)k=1時(shí),fi1+t1-1與fi1可能相鄰(此時(shí)與v關(guān)聯(lián)的面均為3-面). 顯然, 有如下不等式：