稀疏圖平方圖的染色數(shù)上界

張 艷

(天津大學(xué) 應(yīng)用數(shù)學(xué)中心, 天津 300072)

1 引言與主要結(jié)果

本文所考慮的圖均為有限的簡單無向圖.對于一個(gè)圖G, 用E(G),V(G)和Δ(G)分別表示圖G的邊集、頂點(diǎn)集和最大度.用d-點(diǎn)、d--點(diǎn)和d+-點(diǎn)分別表示度數(shù)為d的點(diǎn)、度數(shù)不大于d的點(diǎn)和度數(shù)不小于d的點(diǎn).圖G的k-頂點(diǎn)染色是指映射c:V(G)→{1,2,…,k}; 如果當(dāng)u～v時(shí), 有c(u)≠c(v), 則稱染色c是正常的[1].圖G的平方G2定義為: 頂點(diǎn)集V(G)=V(G2), 并且uv∈E(G2)當(dāng)且僅當(dāng)u和v之間的距離至多為2.平方圖G2的色數(shù)是指使得G2存在正常k-染色的最小整數(shù)k, 用χ(G2)表示.根據(jù)定義, 有χ(G2)≥Δ(G)+1, 其中Δ(G)是指圖G的最大度[2].文獻(xiàn)[3]研究了平面圖的相關(guān)性質(zhì).

猜想1[4]如果G是一個(gè)平面圖, 則:

1) 當(dāng)Δ(G)=3時(shí), 有χ(G2)≤7;

2) 當(dāng)4≤Δ(G)≤7時(shí), 有χ(G2)≤Δ(G)+5;

Wegner[4]證明了如果猜想1是正確的, 則χ(G2)的上界是緊的, 并且如果Δ(G)=3, 則χ(G2)≤8.對于超平面圖, 文獻(xiàn)[5]證明了猜想1.但在平面圖中, 該猜想未得到驗(yàn)證.

圖G的最大平均度定義如下:

(1)

其中V(H)和E(H)分別指子圖H的頂點(diǎn)集和邊集.

定理2[7]設(shè)圖G的最大度Δ(G)=Δ, 則有如下結(jié)論:

2) 如果mad(G)<3,Δ≠5, 則χ(G2)≤Δ+5; 如果mad(G)<3,Δ=5, 則χ(G2)≤11;

Charpentier猜想[8]: 如果mad(G)<4, 則χ(G2)≤2Δ(G).文獻(xiàn)[9]通過構(gòu)造圖G, 使得圖G滿足mad(G)<4, 而χ(G2)=2Δ(G)+2, 進(jìn)而否定了Charpentier猜想.此外, Charpentier[8]還證明了對于充分大的Δ(G), 如果mad(G)<4, 則χ(G2)≤3Δ(G)+3.因此, 有

2Δ(G)+2≤max{χ(G2)|mad(G)<4}≤3Δ(G)+3.

(2)

定理3[8]如果mad(G)<4并且Δ(G)≥8, 則χ(G2)≤3Δ(G)+1.

對于最大度Δ(G)≤5的圖,χ(G2)的上界為3Δ(G)+1, 并且該上界是緊的[8].

定義1在圖G中, 若存在一個(gè)頂點(diǎn)的排序σ:v1,v2,…,vn, 使得對任意的vi(2≤i≤n), |vj:vi～vj,j

本文主要結(jié)果如下:

定理4如果mad(G)<4且Δ(G)≥7, 則χ(G2)≤3Δ(G)+1.

定理5如果mad(G)≤4且Δ(G)≥8, 則χ(G2)≤3Δ(G)+5.

2 定理4的證明

要證明定理4, 只需證明對任意的圖G滿足mad(G)<4且Δ≥7時(shí),G2是3Δ-退化的即可.用反證法, 假設(shè)圖G是滿足mad(G)<4且Δ≥7邊數(shù)最少的極小反例,G2不是3Δ-退化的.先令G中每個(gè)頂點(diǎn)的初始權(quán)重為w(v)=d(v)-4, 由于mad(G)<4, 因而初始總權(quán)重為負(fù); 然后利用權(quán)轉(zhuǎn)移規(guī)則, 將頂點(diǎn)間的權(quán)重進(jìn)行相互轉(zhuǎn)移, 計(jì)算經(jīng)過權(quán)重轉(zhuǎn)移后的總權(quán)重, 如果是非負(fù)的, 則得矛盾.在每個(gè)頂點(diǎn)權(quán)重轉(zhuǎn)移過程中, 需找出在圖G中所規(guī)避的構(gòu)型.

2.1 相關(guān)命題

定義2設(shè)v是圖G的d點(diǎn), 用di(v)表示點(diǎn)v在圖G中i鄰域的個(gè)數(shù)(i=2,3).當(dāng)d(v)≥4時(shí), 對頂點(diǎn)定義如下:

1) 如果d(v)-d2(v)≥7, 則v是好頂點(diǎn).

2) 如果d(v)-d2(v)=6, 則v是弱好頂點(diǎn).

3) 如果d(v)-d2(v)=5, 則v是A型弱壞頂點(diǎn).當(dāng)d3(v)=0時(shí),v稱為A型第一類的; 當(dāng)1≤d3(v)≤3時(shí),v稱為A型第二類的.

4) 如果d(v)-d2(v)=4, 則v是B型弱壞頂點(diǎn).當(dāng)d3(v)=0時(shí),v稱為B型第一類的; 當(dāng)d3(v)=1時(shí),v稱為B型第二類的.

5) 如果d(v)-d2(v)=3, 則v是壞頂點(diǎn).

首先假設(shè)圖G是極小反例, 即圖G滿足mad(G)<4并且Δ≥7, 但G2不是3Δ-退化的.根據(jù)圖G的極小性, 在圖G中刪除某條uv邊后(Guv)2是3Δ-退化的, 最后只需證明G2是3Δ-退化的, 得矛盾.

命題1圖G中的每個(gè)4+-頂點(diǎn)都是定義2中的一種.

證明: 假設(shè)G中的頂點(diǎn)v既不是壞頂點(diǎn), 也不是B型弱壞頂點(diǎn)、A型弱壞頂點(diǎn)、弱好頂點(diǎn)和好頂點(diǎn), 則根據(jù)定義有d(v)-d2(v)≤2, 或者d(v)-d2(v)=4并且d3(v)≥2, 或者d(v)-d2(v)=5并且d3(v)≥4.

對于第一種情形, 因?yàn)閐(v)≥4, 所以v有2鄰域, 記為w.根據(jù)圖G的極小性, (Gvw)2是3Δ-退化的.假設(shè)σ是(Gvw)2的好排序, 可先從σ中刪除v及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)v, 排在點(diǎn)v之前出現(xiàn)的鄰域個(gè)數(shù)至多為2Δ+Δ-2=3Δ-2.對于每個(gè)2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是3Δ-退化的, 矛盾.

對于第二種情形, 令w1,w2分別是v的兩個(gè)3鄰域.根據(jù)圖G的極小性, (Gvw1)2是3Δ-退化的.假設(shè)σ是(Gvw1)2的好排序, 可做如下操作: 先從σ中刪除v,w1,w2及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)v, 排在點(diǎn)v之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為2Δ+Δ-4+4=3Δ.對于wi(i=1,2), 出現(xiàn)在其之前且與其相鄰的頂點(diǎn)至多有(2Δ+4)個(gè).最后對于2頂點(diǎn), 與之相鄰且出現(xiàn)在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是3Δ-退化的, 矛盾.

對于第三種情形, 令w1,w2,w3,w4分別是v的3鄰域.根據(jù)圖G的極小性, (Gvw1)2是3Δ-退化的.假設(shè)σ是(Gvw1)2的好排序, 可做如下操作： 先從σ中刪除v,w1,w2,w3,w4及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)v, 排在點(diǎn)v之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為Δ+Δ-5+8=2Δ+3.對于wi(i=1,2,3,4), 與其相鄰且出現(xiàn)在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ+5.最后對于2頂點(diǎn), 與其相鄰且出現(xiàn)在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是3Δ-退化的, 矛盾.證畢.

命題2在圖G中, 3--點(diǎn)不與3--點(diǎn)相鄰.

證明: 設(shè)u,v是圖G中兩個(gè)相鄰的3--點(diǎn).根據(jù)圖G的極小性, (Guv)2是3Δ-退化的.假設(shè)σ是(Guv)2的好排序, 可先從σ中刪除u和v, 形成新的排序σ′, 然后在σ′中將u和v依次加回.顯然, 與u相鄰并且排在u前面的頂點(diǎn)個(gè)數(shù)至多為2Δ+3,v同理.因此G2是3Δ-退化的, 矛盾.證畢.

命題3在圖G中, 壞頂點(diǎn)不與3點(diǎn)相鄰, 并且其4+鄰域點(diǎn)不是壞頂點(diǎn).

證明： 設(shè)v是圖G的壞頂點(diǎn),u是與v相鄰的3頂點(diǎn).根據(jù)圖G的極小性, (Gvu)2是3Δ-退化的.假設(shè)σ是(Gvu)2的好排序, 可先從σ中刪除v和u及v所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回來.首先對于點(diǎn)v, 出現(xiàn)在點(diǎn)v之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為2Δ+Δ-3+2=3Δ-1.對于點(diǎn)u, 排在其之前的鄰域至多有(2Δ+3)個(gè).最后對于2頂點(diǎn), 排在其之前且與其相鄰的頂點(diǎn)至多有2Δ個(gè).因此G2是3Δ-退化的, 矛盾.

假設(shè)x是圖G的壞頂點(diǎn), 并且x是v的4+鄰域點(diǎn),w是v的2鄰域.根據(jù)圖G的極小性, (Gvw)2是3Δ-退化的.假設(shè)σ是(Gvw)2的好排序, 可先從σ中刪除v及v和x所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)v, 排在點(diǎn)v之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為2Δ+Δ-3+3=3Δ.對于(2Δ-6)個(gè)2鄰域的每個(gè)點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ+4+2Δ-6=3Δ-2.因此G2是3Δ-退化的, 矛盾.證畢.

命題4如果v是圖G中B型弱壞頂點(diǎn)u的壞鄰域, 則v至少有2個(gè)好鄰域.

證明: 假設(shè)w(w≠u)是v的鄰域, 并且w不是好頂點(diǎn).因?yàn)関是壞鄰域, 所以v有2鄰域x.根據(jù)圖G的極小性, (Gvx)2是3Δ-退化的.假設(shè)σ是(Gvx)2的好排序, 可先從σ中刪除點(diǎn)v及v和w所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.首先對于點(diǎn)v, 與點(diǎn)v相鄰并且排在之前的頂點(diǎn)個(gè)數(shù)至多為

Δ-3+4+Δ+d(w)-d2(w)=2Δ+1+d(w)-d2(w)≤2Δ+7

(因?yàn)閣不是好頂點(diǎn), 所以d(w)-d2(w)≤6).此外, 與2頂點(diǎn)相鄰且排在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是3Δ-退化的, 矛盾.證畢.

命題5在圖G中, 每個(gè)B型第一類的弱壞頂點(diǎn)至多有2個(gè)壞鄰域.

證明: 設(shè)u是B型第一類的弱壞頂點(diǎn), 假設(shè)u至少有3個(gè)壞鄰域, 記為v1,v2,v3.由圖G的極小性, (Guv1)2是3Δ-退化的.假設(shè)σ是(Guv1)2的好排序, 可先從σ中刪除u,v1,v2,v3及其所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于vi(i=1,2,3), 排在vi之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為2Δ+Δ-3+3=3Δ.對于點(diǎn)u, 與之相鄰且排在之前的頂點(diǎn)個(gè)數(shù)至多為Δ-4+Δ+3×3=2Δ+5.對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是3Δ-退化的, 矛盾.證畢.

命題6在圖G中, 沒有好鄰域但有壞鄰域的B型第一類弱壞頂點(diǎn)至少有1個(gè)弱好鄰域.

證明: 設(shè)u是沒有好鄰域但有壞鄰域的B型第一類弱壞頂點(diǎn), 且u沒有弱好鄰域, 記其中的1個(gè)壞鄰域?yàn)関1, 其他鄰域?yàn)関2,v3,v4.由圖G的極小性, (Guv1)2是3Δ-退化的.假設(shè)σ是(Guv1)2的好排序, 可做如下操作: 先從σ中刪除u,v1及u,v1,v2,v3,v4所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.首先對于v1, 排在其之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為2Δ+Δ-3+3=3Δ.對于點(diǎn)u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為

(因?yàn)関i(i=2,3,4)既不是好鄰域也不是弱好鄰域, 所以d(vi)-d2(vi)≤5).最后對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是3Δ-退化的, 矛盾.證畢.

命題7每個(gè)B型第二類的弱壞頂點(diǎn)至多有1個(gè)壞鄰域.

證明: 設(shè)u是B型第二類的弱壞頂點(diǎn), 且u至少有2個(gè)壞鄰域, 記為v1和v2, 令w是u的3鄰域.由圖G的極小性, (Guw)2是3Δ-退化的.假設(shè)σ是(Guw)2的好排序, 可做如下操作： 先從σ中刪除u和w及u,v1,v2所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.首先對于點(diǎn)u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-4+Δ+2×3+2=2Δ+4.其次, 對于3頂點(diǎn)w, 與w相鄰且排在其之前的頂點(diǎn)至多有(2Δ+4)個(gè).最后對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是3Δ-退化的, 矛盾.證畢.

命題8在圖G中, 沒有好鄰域的B型第二類弱壞頂點(diǎn)至少有2個(gè)弱好鄰域; 有壞鄰域且僅有1個(gè)好鄰域的B型第二類弱壞頂點(diǎn)至少有1個(gè)弱好鄰域.

證明: 設(shè)u是圖G中沒有好鄰域的B型第二類弱壞頂點(diǎn), 且u至多有1個(gè)弱好鄰域.令w是u的3鄰域, 其他鄰域?yàn)関i(i=1,2,3).由圖G的極小性, (Guw)2是3Δ-退化的.假設(shè)σ是(Guw)2的好排序, 可做如下操作: 先從σ中刪除u和w及u,v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.如果u有1個(gè)弱好鄰域, 記為v1, 則與u相鄰且排在u之前的頂點(diǎn)個(gè)數(shù)至多為

Δ-2+d(v1)-d2(v1)+d(v2)-d2(v2)+d(v3)-d2(v3)≤Δ-2+6+2×5=Δ+14

(因?yàn)関i(i=2,3)既不是好鄰域也不是弱好鄰域, 所以d(vi)-d2(vi)≤5); 如果u沒有弱好鄰域, 則與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為

Δ-2+d(v1)-d2(v1)+d(v2)-d2(v2)+d(v3)-d2(v3)≤Δ-2+5×3=Δ+13

(因?yàn)関i(i=1,2,3)既不是好鄰域也不是弱好鄰域, 所以d(vi)-d2(vi)≤5).此外, 對于3頂點(diǎn)w, 與w相鄰且排在其之前的頂點(diǎn)至多有(2Δ+4)個(gè).對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是3Δ-退化的, 矛盾.

同理, 設(shè)u′是圖G中有壞鄰域且僅有1個(gè)好鄰域的B型第二類弱壞頂點(diǎn), 且u′不存在弱好鄰域.令w′是u′的3鄰域, 其他鄰域?yàn)槠渲惺莡′唯一的好鄰域,是u′的壞鄰域.因?yàn)閡′不存在弱好鄰域, 所以既不是好頂點(diǎn)也不是弱好頂點(diǎn).由圖G的極小性, (Gu′w′)2是3Δ-退化的.假設(shè)σ是(Gu′w′)2的好排序, 可做如下操作： 先從σ中刪除u′和w′及所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)u′, 與u′相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為

命題9在圖G中, 設(shè)A型第一類弱壞頂點(diǎn)為u, 且其鄰域?yàn)関i(i=1,2,3,4,5).令a=|{vi:vi是有2個(gè)好鄰域的壞頂點(diǎn)}|,b=|{vi:vi是至多有1個(gè)好鄰域的壞頂點(diǎn)}|, 則有以下幾種情形:

1) 當(dāng)a=0時(shí),b≤3;

2) 當(dāng)a=1時(shí),b≤2;

3) 當(dāng)a=2時(shí),b≤2;

4) 當(dāng)a=3時(shí),b≤1.

證明: 1) 當(dāng)a=0時(shí), 假設(shè)b≥4, 令至多有1個(gè)好鄰域的壞頂點(diǎn)分別為v1,v2,v3,v4, 并且u與vi(i=1,2,3,4)相鄰.根據(jù)圖G的極小性, (Guv1)2是3Δ-退化的.假設(shè)σ是(Guv1)2的好排序, 可先從σ中刪除u,v1,v2,v3,v4及其所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.因?yàn)関i(i=1,2,3,4)是至多有1個(gè)好鄰域的壞頂點(diǎn), 所以vi存在不是好頂點(diǎn)的鄰域, 記為zi.在尋找與vi相鄰且排在其之前頂點(diǎn)的個(gè)數(shù)時(shí)需刪除zi的2鄰域.在σ′中, 與vi相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為

Δ-3+4+Δ+d(zi)-d2(zi)≤2Δ+1+6=2Δ+7≤3Δ

(因?yàn)閦i不是好頂點(diǎn), 所以d(zi)-d2(zi)≤6).對于點(diǎn)u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-5+Δ+4×3=2Δ+7.對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是3Δ-退化的, 矛盾.

2) 當(dāng)a=1時(shí), 假設(shè)b≥3, 令有2個(gè)好鄰域的壞頂點(diǎn)為v1, 至多有1個(gè)好鄰域的壞頂點(diǎn)為v2,v3,v4, 并且u與vi(i=1,2,3,4)相鄰.根據(jù)圖G的極小性, (Guv2)2是3Δ-退化的.假設(shè)σ是(Guv2)2的好排序, 可先從σ中刪除u,v2,v3,v4及其與v1所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.因?yàn)関i(i=2,3,4)是至多有1個(gè)好鄰域的壞頂點(diǎn), 與第一種情形類似.對于u, 在σ′中, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-5+Δ+4×3=2Δ+7.對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是3Δ-退化的, 矛盾.

3) 當(dāng)a=2時(shí), 假設(shè)b≥3, 令有2個(gè)好鄰域的壞頂點(diǎn)為v1和v2, 至多有1個(gè)好鄰域的壞頂點(diǎn)為v3,v4,v5, 并且u與vi(i=1,2,3,4,5)相鄰.根據(jù)圖G的極小性,(Guv3)2是3Δ-退化的.假設(shè)σ是(Guv3)2的好排序, 可先從σ中刪除u,v3,v4,v5及其與v1,v2所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.因?yàn)関i(i=3,4,5)是至多有一個(gè)好鄰域的壞頂點(diǎn), 與第一種情形類似.在σ′中, 對于u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-5+5×3=Δ+10.對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是3Δ-退化的, 矛盾.

4) 當(dāng)a=3時(shí), 假設(shè)b=2, 令有2個(gè)好鄰域的壞頂點(diǎn)為v1,v2,v3, 至多有1個(gè)好鄰域的壞頂點(diǎn)為v4和v5, 并且u與vi(i=1,2,3,4,5)相鄰.根據(jù)圖G的極小性, (Guv4)2是3Δ-退化的.假設(shè)σ是(Guv4)2的好排序, 可先從σ中刪除u,v4,v5及其與v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.因?yàn)関i(i=4,5)是至多有1個(gè)好鄰域的壞頂點(diǎn), 與第一種情形類似.在σ′中, 對于u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-5+5×3=Δ+10.對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是3Δ-退化的, 矛盾.證畢.

命題10設(shè)u是圖G中A型第二類的弱壞頂點(diǎn), 當(dāng)d3(u)=1時(shí),u至多有2個(gè)壞鄰域; 當(dāng)d3(u)=2時(shí),u至多有一個(gè)壞鄰域; 當(dāng)d3(u)=3時(shí),u沒有壞鄰域.

證明: 當(dāng)d3(u)=1時(shí), 假設(shè)u至少有3個(gè)壞鄰域v1,v2,v3, 且u的3鄰域?yàn)閤.根據(jù)圖G的極小性, (Gux)2是3Δ-退化的.假設(shè)σ是(Gux)2的好排序, 可先從σ中刪除u和x及u,v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-5+Δ+3×3+2=2Δ+6.對于3度頂點(diǎn)x, 與之相鄰且排在其之前的頂點(diǎn)至多有(2Δ+5)個(gè).對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是3Δ-退化的, 矛盾.

當(dāng)d3(u)=2時(shí), 假設(shè)u至少有2個(gè)壞鄰域v1,v2, 且u的2個(gè)3鄰域分別為w1和w2.根據(jù)圖G的極小性, (Guw1)2是3Δ-退化的.假設(shè)σ是(Guw1)2的好排序, 可先從σ中刪除u,w1,w2及u,v1,v2所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-5+Δ+2×3+2×2=2Δ+5.對于wi(i=1,2), 與之相鄰且排在其之前的頂點(diǎn)至多有(2Δ+5)個(gè).對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是3Δ-退化的, 矛盾.

當(dāng)d3(u)=3時(shí), 假設(shè)u存在壞鄰域v1, 令u的3鄰域分別為w1,w2,w3.根據(jù)圖G的極小性, (Guw1)2是3Δ-退化的.假設(shè)σ是(Guw1)2的好排序, 可先從σ中刪除u,w1,w2,w3及u和v1所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-5+Δ+3+2×3=2Δ+4.對于wi(i=1,2,3), 與之相鄰且排在其之前的頂點(diǎn)至多有(2Δ+5)個(gè).最后對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是3Δ-退化的, 矛盾.證畢.

2.2 權(quán)轉(zhuǎn)移規(guī)則

因?yàn)閙ad(G)<4, 所以有

(3)

令每個(gè)頂點(diǎn)的初始權(quán)重為w(v)=d(v)-4, 易知圖G的初始總權(quán)重是負(fù)的.下面制定一些權(quán)重轉(zhuǎn)移規(guī)則, 使得頂點(diǎn)間經(jīng)過權(quán)重轉(zhuǎn)移后, 圖G中每個(gè)頂點(diǎn)的權(quán)重是非負(fù)的, 進(jìn)而圖G的總權(quán)重是非負(fù)的, 形成矛盾.

下面計(jì)算經(jīng)過權(quán)重轉(zhuǎn)移后各頂點(diǎn)的最終權(quán)重.

2.2.1 3--點(diǎn) 根據(jù)權(quán)轉(zhuǎn)移規(guī)則1,G中的每個(gè)2頂點(diǎn)會從其每個(gè)鄰域接收1的權(quán)重, 而且不會失去任何權(quán)重, 因此其最終權(quán)重是w′(v)=2-4+2×1=0.

2.2.2 壞頂點(diǎn) 令v是圖G的壞頂點(diǎn), 根據(jù)權(quán)轉(zhuǎn)移規(guī)則1,v將權(quán)重給相鄰的2鄰域后,v的剩余權(quán)重為-1.此外, 注意到壞頂點(diǎn)不是好頂點(diǎn)和弱好頂點(diǎn), 根據(jù)命題3,v不與3點(diǎn)相鄰并且v沒有壞鄰域, 因此v不會再失去任何權(quán)重.

2.2.3B型弱壞頂點(diǎn) 令v是圖G的B型弱壞頂點(diǎn).

1) 如果v是B型第一類的, 則根據(jù)權(quán)轉(zhuǎn)移規(guī)則1,v將權(quán)重給相鄰的2鄰域后,v的剩余權(quán)重是0.如果v沒有壞鄰域, 則v不會再失去任何權(quán)重,v的權(quán)重是非負(fù)的; 如果v有壞鄰域, 則根據(jù)命題4和命題5,v至多有2個(gè)壞鄰域, 而且這2個(gè)壞鄰域都至少有2個(gè)好鄰域, 由權(quán)轉(zhuǎn)移規(guī)則4,v最多再失去的權(quán)重.此時(shí), 若v有好鄰域, 則根據(jù)權(quán)轉(zhuǎn)移規(guī)則5,v會接收來自好鄰域的權(quán)重, 因此其最終權(quán)重是非負(fù)的.否則,v沒有好鄰域但v有壞鄰域, 根據(jù)命題6,v至少有一個(gè)弱好鄰域, 由權(quán)轉(zhuǎn)移規(guī)則6,v會接收來自弱好鄰域的權(quán)重, 因此其最終權(quán)重也是非負(fù)的.

2) 如果v是B型第二類的, 則根據(jù)權(quán)轉(zhuǎn)移規(guī)則1,v將權(quán)重給相鄰的2鄰域和3鄰域后, 其剩余權(quán)重是如果v沒有壞鄰域, 此時(shí)若v有好鄰域, 由權(quán)轉(zhuǎn)移規(guī)則5,v接收來自好鄰域的權(quán)重, 則v的最終權(quán)重是非負(fù)的; 否則v沒有好鄰域, 根據(jù)命題8,v至少有2個(gè)弱好鄰域, 再根據(jù)權(quán)轉(zhuǎn)移規(guī)則6,v會接收來自弱好鄰域的權(quán)重, 因此v的最終權(quán)重也是非負(fù)的; 如果v有壞鄰域, 則根據(jù)命題4和命題7,v至多有1個(gè)壞鄰域, 而且這個(gè)壞鄰域至少有2個(gè)好鄰域, 由權(quán)轉(zhuǎn)移規(guī)則4,v最多需給壞鄰域的權(quán)重.此時(shí), 若v至少有2個(gè)好鄰域, 則根據(jù)權(quán)轉(zhuǎn)移規(guī)則5,v接收來自好鄰域的權(quán)重, 因此v的最終權(quán)重是非負(fù)的.否則, 若v有1個(gè)好鄰域且v有壞鄰域, 則根據(jù)命題8及權(quán)轉(zhuǎn)移規(guī)則5,6,v至少有1個(gè)弱好鄰域, 因此v會分別接收來自好鄰域的權(quán)重及弱好鄰域的權(quán)重,v的最終權(quán)重是非負(fù)的; 若v沒有好鄰域, 則根據(jù)命題8,v至少有2個(gè)弱好鄰域, 由權(quán)轉(zhuǎn)移規(guī)則6, 其會接收來自弱好鄰域的權(quán)重, 因此其最終權(quán)重仍是非負(fù)的.

2.2.4A型弱壞頂點(diǎn) 令v是圖G的A型弱壞頂點(diǎn).

1) 如果v是A型第一類的, 則根據(jù)權(quán)轉(zhuǎn)移規(guī)則1,v將權(quán)重給相鄰的2鄰域后, 其剩余權(quán)重是1.令

a=|{vi:vi～v, 且vi是有2個(gè)好鄰域的壞頂點(diǎn)}|,

b=|{vi:vi～v, 且vi是至多有1個(gè)好鄰域的壞頂點(diǎn)}|.

2) 如果v是A型第二類的, 則當(dāng)d3(v)=1時(shí), 根據(jù)權(quán)轉(zhuǎn)移規(guī)則1,v將權(quán)重給相鄰的2鄰域和3鄰域后, 其剩余權(quán)重是根據(jù)命題10,v至多有2個(gè)壞鄰域, 再由權(quán)轉(zhuǎn)移規(guī)則3,4,v最多會失去的權(quán)重, 因此其最終權(quán)重是非負(fù)的; 當(dāng)d3(v)=2時(shí), 根據(jù)權(quán)轉(zhuǎn)移規(guī)則1,v將權(quán)重給相鄰的2鄰域和3鄰域后, 其剩余權(quán)重是根據(jù)命題10,v至多有1個(gè)壞鄰域, 再由權(quán)轉(zhuǎn)移規(guī)則3,4,v最多會失去的權(quán)重, 因此其最終權(quán)重是非負(fù)的; 當(dāng)d3(v)=3時(shí), 根據(jù)權(quán)轉(zhuǎn)移規(guī)則1,v將權(quán)重給相鄰的2鄰域和3鄰域后, 其剩余權(quán)重是0.根據(jù)命題10,v沒有壞鄰域, 不會再失去權(quán)重, 因此v的最終權(quán)重為0.

綜上可見,v的最終權(quán)重是非負(fù)的.

2.2.5 弱好頂點(diǎn) 令v是圖G的弱好頂點(diǎn).根據(jù)權(quán)轉(zhuǎn)移規(guī)則1,v將權(quán)重給相鄰的2鄰域后, 此時(shí)v的剩余權(quán)重為2.因?yàn)関不是好頂點(diǎn), 根據(jù)權(quán)轉(zhuǎn)移規(guī)則1,3,4,6, 所以v會將權(quán)重給3鄰域、壞鄰域及與之相鄰的B型弱壞頂點(diǎn).因?yàn)閐(v)-d2(v)=6, 所以v至多會失去的權(quán)重, 因此v的最終權(quán)重是非負(fù)的.

2.2.6 好頂點(diǎn) 令v是圖G的好頂點(diǎn), 且記d2(v)是v的2鄰域的個(gè)數(shù).根據(jù)權(quán)轉(zhuǎn)移規(guī)則1,2,3,5, 因?yàn)関是好頂點(diǎn), 所以至多有(d(v)-d2(v))個(gè)鄰域分別會接收來自v的至多的權(quán)重, 因此其最終權(quán)重為

(因?yàn)閐(v)-d2(v)≥7).

通過上述對頂點(diǎn)間的權(quán)重轉(zhuǎn)移, 可得圖G中每個(gè)頂點(diǎn)的最終權(quán)重為非負(fù)的, 因此圖G的最終總權(quán)重也是非負(fù)的, 與初始總權(quán)重是負(fù)的矛盾.

3 定理5的證明

定理5的證明類似定理4, 需找出在圖G中規(guī)避的構(gòu)型.

3.1 相關(guān)命題

定義3設(shè)v是圖G的d點(diǎn), 用di(v)表示點(diǎn)v在圖G中i鄰域的個(gè)數(shù)(i=2,3,4).當(dāng)d(v)≥5時(shí), 對頂點(diǎn)定義如下:

1) 如果d(v)-d2(v)≥8, 則v是優(yōu)頂點(diǎn).

2) 如果d(v)-d2(v)≥7, 則v是好頂點(diǎn).

3) 如果d(v)-d2(v)=6, 則v是弱好頂點(diǎn).

4) 如果d(v)-d2(v)=5, 則v是A型弱壞頂點(diǎn).當(dāng)d3(v)=0時(shí),v稱為A型第一類的; 當(dāng)1≤d3(v)≤2時(shí),v稱為A型第二類的.

5) 如果d(v)-d2(v)=4, 則v是B型弱壞頂點(diǎn).當(dāng)d3(v)=0時(shí),v稱為B型第一類的; 當(dāng)d3(v)=1時(shí),v稱為B型第二類的.

6) 如果d(v)-d2(v)=3, 則v是壞頂點(diǎn).

首先假設(shè)圖G是極小反例, 即圖G滿足mad(G)≤4且Δ≥8, 但G2不是(3Δ+4)-退化的.根據(jù)圖G的極小性, 在圖G中刪除某條uv邊后(Guv)2是(3Δ+4)-退化的, 最后只需證明G2是(3Δ+4)-退化的, 得到矛盾.

命題11圖G中的每個(gè)5+-頂點(diǎn)都是定義3中的一種.

證明: 假設(shè)圖G中的頂點(diǎn)v既不是壞頂點(diǎn), 也不是A型弱壞頂點(diǎn)、B型弱壞頂點(diǎn)、弱好頂點(diǎn)和好頂點(diǎn), 則根據(jù)定義有d(v)-d2(v)≤2, 或者d(v)-d2(v)=4并且d3(v)≥2, 或者d(v)-d2(v)=5并且d3(v)≥3.

對于第一種情形, 因?yàn)閐(v)≥5, 所以v有2° 鄰域, 記為w.根據(jù)圖G的極小性, (Gvw)2是(3Δ+4)-退化的.假設(shè)σ是(Gvw)2的好排序, 可先從σ中刪除v及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)v, 排在點(diǎn)v之前出現(xiàn)的鄰域個(gè)數(shù)至多為2Δ+Δ-2=3Δ-2.對于每個(gè)2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.

對于第二種情形, 令w1,w2分別是v的2個(gè)3鄰域.根據(jù)圖G的極小性, (Gvw1)2是(3Δ+4)-退化的.假設(shè)σ是(Gvw1)2的好排序, 可先從σ中刪除v,w1,w2及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)v, 排在點(diǎn)v之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為2Δ+Δ-4+4=3Δ.對于wi(i=1,2), 排在其之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為2Δ+4.對于2頂點(diǎn), 與之相鄰且出現(xiàn)在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是(3Δ+4)-退化的, 矛盾.

對于第三種情形, 令w1,w2,w3分別是v的3鄰域.根據(jù)圖G的極小性, (Gvw1)2是(3Δ+4)-退化的.假設(shè)σ是(Gvw1)2的好排序, 可先從σ中刪除v,w1,w2,w3及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)v, 出現(xiàn)在點(diǎn)v之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為2Δ+Δ-5+6=3Δ+1.對于wi(i=1,2,3), 出現(xiàn)在其之前的鄰域個(gè)數(shù)至多為2Δ+5.對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題12在圖G中, 4--點(diǎn)不與4--點(diǎn)相鄰.

證明: 設(shè)u,v是圖G中兩個(gè)相鄰的4--頂點(diǎn).根據(jù)圖G的極小性, (Guv)2是(3Δ+4)-退化的.假設(shè)σ是(Guv)2的好排序, 可先從σ中刪除u和v, 形成新的排序σ′, 然后在σ′中將u和v依次加回.顯然, 對于點(diǎn)u, 與u相鄰并且排在其之前的頂點(diǎn)至多有(3Δ+4)個(gè),v同理.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題13在圖G中, 壞頂點(diǎn)v既不與3點(diǎn)相鄰也不與4點(diǎn)相鄰, 并且v的5+鄰域點(diǎn)不是壞頂點(diǎn).

證明: 設(shè)u是與v相鄰的3頂點(diǎn).根據(jù)圖G的極小性, (Gvu)2是(3Δ+4)-退化的.假設(shè)σ是(Gvu)2的好排序, 可先從σ中刪除v和u及v所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)v, 出現(xiàn)在v之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為2Δ+Δ-3+2=3Δ-1.對于3點(diǎn)u, 排在u之前的鄰域至多有(2Δ+3)個(gè).對于2頂點(diǎn), 排在其之前且與其相鄰的點(diǎn)至多有2Δ個(gè).因此G2是(3Δ+4)-退化的, 矛盾.

設(shè)w是與v相鄰的4頂點(diǎn).根據(jù)圖G的極小性, (Gvw)2是(3Δ+4)-退化的.假設(shè)σ是(Gvw)2的好排序, 可先從σ中刪除v和w及v所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)v, 排在點(diǎn)v之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為2Δ+Δ-3+3=3Δ.對于4點(diǎn)w, 排在w之前的鄰域至多有(3Δ+3)個(gè).對于2頂點(diǎn), 排在其之前且與其相鄰的點(diǎn)至多有2Δ個(gè).因此G2是(3Δ+4)-退化的, 矛盾.

假設(shè)x是圖G中的壞頂點(diǎn), 并且x是v的5+鄰域點(diǎn),w是v的2鄰域.根據(jù)圖G的極小性, (Gvw)2是(3Δ+4)-退化的.假設(shè)σ是(Gvw)2的好排序, 可先從σ中刪除v及v和x所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)v, 排在點(diǎn)v之前且與其相鄰的頂點(diǎn)個(gè)數(shù)至多為2Δ+Δ-3+3=3Δ.對于(2Δ-6)個(gè)2鄰域的每個(gè)點(diǎn), 與之相鄰且出現(xiàn)在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ+4+2Δ-6=3Δ-2.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題14如果v是圖G中A型弱壞頂點(diǎn)u的壞鄰域, 則v至少有2個(gè)優(yōu)鄰域.同理, 若v′是圖G中B型弱壞頂點(diǎn)u′的壞鄰域, 則v′至少有2個(gè)優(yōu)鄰域.

證明: 假設(shè)w(w≠u)是v的鄰域, 并且w不是優(yōu)頂點(diǎn).因?yàn)関是壞鄰域, 所以v有2鄰域x.根據(jù)圖G的極小性, (Gvx)2是(3Δ+4)-退化的.假設(shè)σ是(Gvx)2的好排序, 可先從σ中刪除v及v和w所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.首先對于點(diǎn)v, 與v相鄰并且排在其之前的頂點(diǎn)個(gè)數(shù)至多為

Δ-3+5+Δ+d(w)-d2(w)≤ 2Δ+2+7=2Δ+9

(因?yàn)閣不是優(yōu)頂點(diǎn), 所以d(w)-d2(w)≤7).此外, 與2頂點(diǎn)相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.

同理可證v′至少有2個(gè)優(yōu)鄰域.證畢.

命題15每個(gè)B型第一類的弱壞頂點(diǎn)至多有2個(gè)壞鄰域.

證明: 設(shè)u是B型第一類的弱壞頂點(diǎn), 且u至少有3個(gè)壞鄰域, 分別記為v1,v2,v3.因?yàn)閡是B型第一類弱壞頂點(diǎn), 所以u有2鄰域x, 由圖G的極小性, (Gux)2是(3Δ+4)-退化的.假設(shè)σ是(Gux)2的好排序, 可先從σ中刪除u及u,v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)u, 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-4+Δ+3×3=2Δ+5.對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題16在圖G中, 沒有好鄰域的B型第一類弱壞頂點(diǎn)至少有1個(gè)弱好鄰域; 沒有好鄰域但至少有1個(gè)弱好鄰域的B型第一類弱壞頂點(diǎn)至多有1個(gè)壞鄰域.

證明: 設(shè)u是沒有好鄰域的B型第一類弱壞頂點(diǎn), 且u沒有弱好鄰域, 其鄰域設(shè)為v1,v2,v3,v4.因?yàn)閡是B型第一類弱壞頂點(diǎn), 所以u有2鄰域x, 由圖G的極小性, (Gux)2是(3Δ+4)-退化的.假設(shè)σ是(Gux)2的好排序, 可先從σ中刪除u及u,v1,v2,v3,v4所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為

(因?yàn)関i(i=1,2,3,4)既不是弱好鄰域也不是好鄰域, 所以d(vi)-d2(vi)≤5).對于2頂點(diǎn), 與之相鄰且排在其之前的點(diǎn)至多有2Δ個(gè).因此G2是(3Δ+4)-退化的, 矛盾.

設(shè)沒有好鄰域但至少有1個(gè)弱好鄰域的B型第一類弱壞頂點(diǎn)為u′, 且其至少有2個(gè)壞鄰域v1和v2, 其他鄰域?yàn)閦和w, 其中z是弱好鄰域.因?yàn)閡′是B型第一類弱壞頂點(diǎn), 所以u′有2鄰域x′, 由圖G的極小性, (Gu′x′)2是(3Δ+4)-退化的.假設(shè)σ是(Gu′x′)2的好排序, 可先從σ中刪除u′及u′,w,v1,v2,z所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于u′, 與u′相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為

(因?yàn)閣不是好鄰域, 所以d(w)-d2(w)≤6).對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題17在圖G中, 每個(gè)B型第二類的弱壞頂點(diǎn)u至少有1個(gè)好鄰域, 此外u至多有1個(gè)壞鄰域.

證明: 設(shè)u沒有好鄰域, 令w是u的3鄰域, 其他鄰域?yàn)関1,v2,v3.由圖G的極小性, (Guw)2是(3Δ+4)-退化的.假設(shè)σ是(Guw)2的好排序, 可先從σ中刪除u和w及u,v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為

Δ-4+2+d(v1)-d2(v1)+d(v2)-d2(v2)+d(v3)-d2(v3)≤Δ-2+6×3=Δ+16

(因?yàn)関i(i=1,2,3)不是好頂點(diǎn), 所以d(vi)-d2(vi)≤6).此外, 對于3頂點(diǎn)w, 與w相鄰且排在其之前的頂點(diǎn)至多有(2Δ+4)個(gè).對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是(3Δ+4)-退化的, 矛盾.

設(shè)u至少有2個(gè)壞鄰域, 記為v1和v2.由圖G的極小性, (Guw)2是(3Δ+4)-退化的.假設(shè)σ是(Guw)2的好排序, 可先從σ中刪除u和w及u,v1,v2所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為

Δ-4+2+d(v1)-d2(v1)+d(v2)-d2(v2)+Δ=2Δ+4.

命題18在圖G中, 有且僅有1個(gè)好鄰域的B型第二類弱壞頂點(diǎn)至少有1個(gè)弱好鄰域.

證明: 設(shè)u是有且僅有1個(gè)好鄰域的B型第二類弱壞頂點(diǎn), 且u沒有弱好鄰域, 令w是u的3鄰域,v1為u的好鄰域, 其他鄰域?yàn)関2和v3.由圖G的極小性, (Guw)2是(3Δ+4)-退化的.假設(shè)σ是(Guw)2的好排序, 可先從σ中刪除u和w及u,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為

Δ-4+2+Δ+d(v2)-d2(v2)+d(v3)-d2(v3)≤Δ-2+Δ+2×5=2Δ+8

(因?yàn)関i(i=2,3)既不是好鄰域又不是弱好鄰域, 所以d(vi)-d2(vi)≤5).此外, 對于3頂點(diǎn)w, 與w相鄰且排在其之前的頂點(diǎn)至多有(2Δ+4)個(gè).對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有2Δ個(gè).因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題19在圖G中, 每個(gè)A型第一類的弱壞頂點(diǎn)至多有4個(gè)壞鄰域.

證明: 設(shè)u是圖G中A型第一類的弱壞頂點(diǎn), 且u至少有5個(gè)壞鄰域v1,v2,v3,v4,v5.根據(jù)圖G的極小性, (Guv1)2是(3Δ+4)-退化的.假設(shè)σ是(Guv1)2的好排序, 可先從σ中刪除u,v1,v2,v3,v4,v5及其所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于vi(i=1,2,3,4,5), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ+Δ-3+4=3Δ+1.對于u, 與u相鄰且排在其之前的頂點(diǎn)至多有(Δ-5+5×3=Δ+10)個(gè).對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題20設(shè)u是圖G中A型第二類的弱壞頂點(diǎn), 當(dāng)d3(u)=1時(shí),u至多有2個(gè)壞鄰域; 當(dāng)d3(u)=2時(shí),u至多有1個(gè)壞鄰域.

證明: 當(dāng)d3(u)=1時(shí), 假設(shè)u至少有3個(gè)壞鄰域v1,v2,v3, 記u的3鄰域?yàn)閤.根據(jù)圖G的極小性, (Gux)2是(3Δ+4)-退化的.假設(shè)σ是(Gux)2的好排序, 先從σ中刪除u和x及u,v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-5+Δ+3×3+2=2Δ+6.對于3點(diǎn)x, 與之相鄰且排在其之前的頂點(diǎn)至多有(2Δ+5)個(gè).對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.

當(dāng)d3(u)=2時(shí), 假設(shè)u至少有2個(gè)壞鄰域v1,v2, 記u的3鄰域分別為w1和w2.根據(jù)圖G的極小性, (Guw1)2是(3Δ+4)-退化的.假設(shè)σ是(Guw1)2的好排序, 先從σ中刪除u,w1,w2及u,v1,v2所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于點(diǎn)u, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-5+Δ+2×3+2×2=2Δ+5.對于3點(diǎn)wi(i=1,2), 與之相鄰且排在其之前的頂點(diǎn)至多有(2Δ+5)個(gè).對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題21設(shè)u是圖G的弱好頂點(diǎn), 除u的2鄰域外,u的其他鄰域有以下幾種情形:

1) 若u的鄰域中不存在B型弱壞頂點(diǎn), 則u至多有5個(gè)鄰域或者是3頂點(diǎn)或者是壞頂點(diǎn);

2) 若u的鄰域中存在1個(gè)B型弱壞頂點(diǎn), 則u至多有4個(gè)鄰域或者是3頂點(diǎn)或者是壞頂點(diǎn);

3) 若u的鄰域中存在2個(gè)B型弱壞頂點(diǎn), 則u至多有3個(gè)鄰域或者是3頂點(diǎn)或者是壞頂點(diǎn);

4) 若u的鄰域中存在3個(gè)B型弱壞頂點(diǎn), 則u至多有2個(gè)鄰域或者是3頂點(diǎn)或者是壞頂點(diǎn);

5) 若u的鄰域中存在4個(gè)B型弱壞頂點(diǎn), 則u至多有1個(gè)鄰域或者是3頂點(diǎn)或者是壞頂點(diǎn);

6) 若u的鄰域中存在5個(gè)B型弱壞頂點(diǎn), 則u的鄰域中不存在3頂點(diǎn)或者是壞頂點(diǎn).

證明: 1) 若弱好頂點(diǎn)u不存在B型弱壞鄰域, 則假設(shè)u至少有6個(gè)鄰域v1,v2,v3,v4,v5,v6, 分別是3頂點(diǎn)或者是壞頂點(diǎn).如果v1是3頂點(diǎn), 則根據(jù)圖G的極小性, (Guv1)2是(3Δ+4)-退化的, 故假設(shè)σ是(Guv1)2的好排序; 否則,v1是壞頂點(diǎn), 其2鄰域w, 根據(jù)圖G的極小性, (Gv1w)2是(3Δ+4)-退化的, 故假設(shè)σ是(Gv1w)2的好排序.在這兩種情形下, 均可從σ中刪除u,v1,v2,v3,v4,v5,v6及其所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于vi中的壞頂點(diǎn), 假設(shè)vi(i=1,2,3,4,5,6)是壞頂點(diǎn), 與vi相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ+5+Δ-3=3Δ+2.對于點(diǎn)u, 在σ′中, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-6+6×3=Δ+12.對于vi中剩余的3點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有(2Δ+6)個(gè).對于所有剩余的2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.

2) 若弱好頂點(diǎn)u有1個(gè)B型弱壞鄰域, 則假設(shè)u至少有5個(gè)鄰域是3頂點(diǎn)或者是壞頂點(diǎn), 記為v1,v2,v3,v4,v5.如果v1是3頂點(diǎn), 則根據(jù)圖G的極小性, (Guv1)2是(3Δ+4)-退化的, 故假設(shè)σ是(Guv1)2的好排序; 否則,v1是壞頂點(diǎn), 其有2鄰域w, 根據(jù)圖G的極小性, (Gv1w)2是(3Δ+4)-退化的, 故假設(shè)σ是(Gv1w)2的好排序.在這兩種情形下, 均可從σ中刪除u、3頂點(diǎn)和壞頂點(diǎn)及其與B型弱壞頂點(diǎn)所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點(diǎn)依次加回.對于vi中的壞頂點(diǎn), 同1).對于點(diǎn)u, 在σ′中, 與u相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為Δ-6+1×4+3×5=Δ+13.對于vi中剩余的3點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)至多有(2Δ+6)個(gè).對于2頂點(diǎn), 與之相鄰且排在其之前的頂點(diǎn)個(gè)數(shù)至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.

3)～6)的證明同2), 故略.

3.2 權(quán)轉(zhuǎn)移規(guī)則

因?yàn)閙ad(G)≤4, 所以有

(4)

令每個(gè)頂點(diǎn)的初始權(quán)重為w(v)=d(v)-4, 則易知圖G的初始總權(quán)重是非正的.通過制定一些權(quán)重轉(zhuǎn)移規(guī)則, 使得頂點(diǎn)間經(jīng)過權(quán)重轉(zhuǎn)移后, 圖G中每個(gè)頂點(diǎn)的權(quán)重為正, 進(jìn)而圖G的最終總權(quán)重為正, 構(gòu)成矛盾.

對于圖G中的點(diǎn)v,d2(v)和d4(v)分別表示點(diǎn)v的2鄰域和4鄰域的個(gè)數(shù).令當(dāng)ε1,ε2取足夠小時(shí), 有由D2和D4的定義, 對于任意的點(diǎn)v, 滿足從而可知也成立.

權(quán)轉(zhuǎn)移規(guī)則7: 每個(gè)頂點(diǎn)給權(quán)重1+ε1到其每個(gè)2鄰域, 給權(quán)重到其每個(gè)3鄰域及給權(quán)重ε2到其每個(gè)4鄰域.

下面計(jì)算經(jīng)過權(quán)重轉(zhuǎn)移后各頂點(diǎn)的最終權(quán)重.

3.2.1 4--點(diǎn) 根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,G中的每個(gè)2頂點(diǎn)會從其每個(gè)鄰域接收1+ε1的權(quán)重, 而且不會失去任何權(quán)重, 因此其最終權(quán)重是w′(v)=2-4+2×(1+ε1)=2ε1>0.

3.2.2 壞頂點(diǎn) 令v是圖G的壞頂點(diǎn).根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,v將權(quán)重給相鄰的2鄰域后, 此時(shí)v的剩余權(quán)重為-1-d2(v)ε1.此外, 注意到壞頂點(diǎn)不是好頂點(diǎn)和弱好頂點(diǎn),根據(jù)命題13,v不與3頂點(diǎn)和4頂點(diǎn)相鄰, 并且v沒有壞鄰域, 因此v不會再失去任何權(quán)重.

綜上所述,v的最終權(quán)重為正.

3.2.3B型弱壞頂點(diǎn) 令v是圖G的B型弱壞頂點(diǎn).

1) 如果v是B型第一類的, 則根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,v將權(quán)重給相鄰的2鄰域和4鄰域后,v的剩余權(quán)重是-d2(v)ε1-d4(v)ε2.此外, 根據(jù)命題14和命題15,v至多有2個(gè)壞鄰域, 且每個(gè)壞鄰域至少有2個(gè)優(yōu)鄰域, 由權(quán)轉(zhuǎn)移規(guī)則10,v至多會失去的權(quán)重.如果v有好鄰域, 則根據(jù)權(quán)轉(zhuǎn)移規(guī)則11,v至少會接收來自好鄰域的權(quán)重, 因此v的最終權(quán)重是

2) 如果v是B型第二類的, 則根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,v將權(quán)重給相鄰的2鄰域、3鄰域和4鄰域后, 其剩余權(quán)重是根據(jù)命題14和命題17,v至多有1個(gè)壞鄰域, 而且壞鄰域至少有2個(gè)優(yōu)鄰域, 由權(quán)轉(zhuǎn)移規(guī)則10,v至多會失去的權(quán)重.如果v至少有2個(gè)好鄰域, 則由權(quán)轉(zhuǎn)移規(guī)則11,v至少會接收來自其好鄰域的權(quán)重, 因此v的最終權(quán)重是

3.2.4A型弱壞頂點(diǎn) 令v是圖G的A型弱壞頂點(diǎn).

1) 如果v是A型第一類的, 則根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,v將權(quán)重給相鄰的2鄰域和4鄰域后, 其剩余權(quán)重是1-d2(v)ε1-d4(v)ε2.根據(jù)命題14和命題19,v至多有4個(gè)壞鄰域, 而且壞鄰域至少有2個(gè)優(yōu)鄰域, 由權(quán)轉(zhuǎn)移規(guī)則10,v最多會失去的權(quán)重, 因此其最終權(quán)重是

2) 如果v是A型第二類的, 則當(dāng)d3(v)=1時(shí), 根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,v將權(quán)重給相鄰的2鄰域、3鄰域和4鄰域后, 其剩余權(quán)重是根據(jù)命題14和命題20,v至多有2個(gè)壞鄰域, 而且壞鄰域至少有2個(gè)優(yōu)鄰域, 再由權(quán)轉(zhuǎn)移規(guī)則10,v至多會失去的權(quán)重, 故其最終權(quán)重是

當(dāng)d3(v)=2時(shí), 根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,v將權(quán)重給相鄰的2鄰域、3鄰域和4鄰域后, 其剩余權(quán)重是-d2(v)ε1-d4(v)ε2.根據(jù)命題14和命題20,v至多有1個(gè)壞鄰域, 而且壞鄰域至少有2個(gè)優(yōu)鄰域, 再由權(quán)轉(zhuǎn)移規(guī)則10,v至多會失去的權(quán)重, 故其最終權(quán)重是

3.2.5 弱好頂點(diǎn) 令v是圖G的弱好頂點(diǎn).根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,v將權(quán)重給相鄰的2鄰域和4鄰域后, 此時(shí)v的剩余權(quán)重是2-d2(v)ε1-d4(v)ε2.因?yàn)関不是好頂點(diǎn), 所以根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,9,10,12,v會將權(quán)重給3鄰域、壞鄰域及給與之相鄰的B型弱壞頂點(diǎn).若v的鄰域中不存在B型弱壞頂點(diǎn), 則根據(jù)命題21中1),v至多有5個(gè)鄰域是3頂點(diǎn)或者是壞頂點(diǎn).根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,9,10,v最多會失去的權(quán)重, 因此v的最終權(quán)重是

若v的鄰域中存在1個(gè)B型弱壞頂點(diǎn), 則根據(jù)命題21中2),v至多有4個(gè)鄰域是3頂點(diǎn)或者是壞頂點(diǎn), 根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,9,10,12,v最多會失去的權(quán)重, 因此v的最終權(quán)重是

若v的鄰域中存在2個(gè)B型弱壞頂點(diǎn), 則根據(jù)命題21中3),v至多有3個(gè)鄰域是3頂點(diǎn)或者是壞頂點(diǎn), 根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,9,10,12,v最多會失去的權(quán)重, 因此v的最終權(quán)重是

若v的鄰域中存在3個(gè)B型弱壞頂點(diǎn), 則根據(jù)命題21中4),v至多有2個(gè)鄰域是3頂點(diǎn)或者是壞頂點(diǎn), 根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,9,10,12,v最多會失去的權(quán)重, 因此v的最終權(quán)重是

若v的鄰域中存在4個(gè)B型弱壞頂點(diǎn), 則根據(jù)命題21中5), 則v至多有1個(gè)鄰域是3頂點(diǎn)或者壞頂點(diǎn), 根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,9,10,12,v最多會失去的權(quán)重, 因此v的最終權(quán)重是

若v的鄰域中存在5個(gè)B型弱壞頂點(diǎn), 則根據(jù)命題21中6),v不存在3鄰域或者是壞鄰域, 根據(jù)權(quán)轉(zhuǎn)移規(guī)則12,v會失去的權(quán)重, 因此v的最終權(quán)重是

綜上所述,v的最終權(quán)重為正.

3.2.6 好頂點(diǎn) 令v是圖G的好頂點(diǎn), 并且記d2(v)是v的2鄰域個(gè)數(shù).如果v不是優(yōu)頂點(diǎn), 則對于除去2鄰域外的其他(d(v)-d2(v))個(gè)鄰域, 根據(jù)權(quán)轉(zhuǎn)移規(guī)則7,9,10,11,v會分別給每個(gè)鄰域至多的權(quán)重, 因此其最終權(quán)重是

(因?yàn)閐(v)-d2(v)≥8).

通過上述對頂點(diǎn)間的權(quán)重轉(zhuǎn)移, 得到圖G中每個(gè)頂點(diǎn)的最終權(quán)重為正, 因此圖G的最終總權(quán)重也為正, 與初始總權(quán)重非正矛盾.

衷心感謝天津大學(xué)應(yīng)用數(shù)學(xué)中心彭興老師的鼓勵(lì)和指導(dǎo).