擬平衡二部圖的弱逐點(diǎn)可跡性的若干充分條件

劉 莉，余桂東，袁 慧

（安慶師范大學(xué) 數(shù)理學(xué)院，安徽 安慶 246133）

設(shè)G=G(V,E)為n階簡(jiǎn)單連通圖，頂點(diǎn)集V=V(G)={v1,v2,v3…,vn}，邊集E=E(G)為G的二元重集構(gòu)成的集合。頂點(diǎn)v的度dG(v)是指G中與v關(guān)聯(lián)的邊數(shù)，G的最小度記作δ。G中vi與vj之間的距離記作dG(vi,vj)。在二部圖G(X,Y;E)中，若|X|=|Y|，則G(X,Y;E)為平衡二部圖；若|Y|=|X|-1，則G(X,Y;E)為擬平衡二部圖。設(shè)G是一個(gè)2n階的平衡二部圖，若連續(xù)連接圖G中度和不小于n+2的不同部分的不相鄰點(diǎn)對(duì)，直到?jīng)]有這樣的點(diǎn)對(duì)，則所得到的圖稱為G的Bn+2-閉包，記作圖G的是唯一確定的，與所增加邊的次序無關(guān)，并且在中任意不相鄰點(diǎn)對(duì)u,v均有

圖G鄰接矩陣A(G)的定義是：鄰接矩陣A(G)=[aij]n×n，當(dāng)vi,vj相鄰時(shí)aij=1，當(dāng)vi,vj不相鄰時(shí)aij=0，i,j=1,2,3,…,n，其最大特征值μ(G)稱為G的譜半徑。圖G的無符號(hào)拉普拉斯矩陣Q(G)的定義是：設(shè)D(G)=為圖G的度對(duì)角矩陣，Q(G)=D(G)+A(G)，其最大特征值q(G)被稱為圖G的無符號(hào)拉普拉斯譜半徑。

圖的拓?fù)渲笖?shù)作為化學(xué)圖論里重要的一部分，學(xué)者們大多數(shù)討論的是Wiener指數(shù)[1,2]，Hyper-Wiener指數(shù)[3]以及Harary指數(shù)[4,5]。

一條包含圖G中所有頂點(diǎn)的路（圈）稱為哈密爾頓路（圈）。如果G有哈密爾頓路（圈），則稱G是可跡圖（哈密爾頓圖）。如果在平衡二部圖G=(X,Y;E)中，可以在X中任一點(diǎn)與Y中任一點(diǎn)之間均能找到一條哈密爾頓路，那么該平衡二部圖稱為弱哈密爾頓-連通圖。如果在擬平衡二部圖G=(X,Y;E)中，從X中任一點(diǎn)出發(fā)均能找到一條哈密爾頓路，那么稱該擬平衡二部圖為弱逐點(diǎn)可跡圖。本文沒有提及的知識(shí)請(qǐng)參考文獻(xiàn)[6]。

圖的哈密爾頓問題是NP-完全問題，至今還沒能被完美地解決。而利用圖的譜和拓?fù)渲笖?shù)來刻畫圖的哈密爾頓性已經(jīng)取得了很多成果。如文獻(xiàn)[7]利用原圖的譜半徑給出了具有較大最小度的簡(jiǎn)單圖是哈密爾頓-連通的充分條件。文獻(xiàn)[8]根據(jù)圖G的邊數(shù)、譜半徑和無符號(hào)拉普拉斯譜半徑，分別給出哈密爾頓連通圖以及從任意點(diǎn)出發(fā)都可跡圖的一些充分條件。文獻(xiàn)[9]利用圖的Hyper-Wiener指數(shù)來給出一般連通圖是哈密爾頓-連通的充分條件，以及在δ(G)≥k時(shí)一般連通圖是可跡的和哈密爾頓的充分條件。文獻(xiàn)[10]研究了當(dāng)δ(G)≥k時(shí)，利用圖的Wiener指數(shù)和Harary指數(shù)得出一般連通圖是哈密爾頓的以及是可跡的充分條件。在目前文獻(xiàn)資料中，僅有文獻(xiàn)[11]利用簡(jiǎn)單平衡二部圖的一些度、邊數(shù)和譜半徑條件來提出圖是弱哈密爾頓連通的充分條件，關(guān)于擬平衡二部圖是弱逐點(diǎn)可跡的這個(gè)問題至今還沒有學(xué)者研究。受此啟發(fā)，本文首先根據(jù)平衡二部圖是弱哈密爾頓-連通的邊充分條件以得到擬平衡二部圖是弱逐點(diǎn)可跡的邊充分條件；其次根據(jù)譜半徑及無符號(hào)拉普拉斯譜半徑分別給出了擬平衡二部圖是弱逐點(diǎn)可跡的充分條件；最后利用Wiener指數(shù)、Hyper-Wiener指數(shù)以及Harary指數(shù)分別給出了擬平衡二部圖是弱逐點(diǎn)可跡的充分條件。

1 預(yù)備知識(shí)

下面介紹本文需要用到的相關(guān)引理。

引理1[11]2n階的平衡二部圖G是弱哈密爾頓-連通的，當(dāng)且僅當(dāng)是弱哈密爾頓-連通的。

引理2[11]設(shè)平衡二部圖G=G(X,Y;E)的階數(shù)為2n，G=如果n≥2k，k≥1，e(G) >n(n-k)+k(k+1)，那么G中含有一個(gè)2n-k+1階的完全二部圖。如果δ(G)≥k，那么Kn,n-k+1?G。

引理3[11]設(shè)平衡二部圖G=G(X,Y;E)的階數(shù)是2n如果δ(G)≥k≥1，n≥2k，e(G)>n(n-k)+k(k+1)，則G是弱哈密爾頓-連通的。

引理4[12]在二部圖G=(X,Y;E)中μ(G)≤

引理5[12]在2n階的平衡二部圖G=(X,Y;E)中

引理6[13]若在2n-1 階擬平衡二部圖G=(X,Y;E)中，Wiener 指數(shù)的不等式W(G)≥5n2-7n+2-2e(G)等號(hào)成立時(shí)，當(dāng)且僅當(dāng)G中任意兩個(gè)不相鄰的點(diǎn)x,y∈V(G)，如果x,y屬于不同的分部，則d(x,y)=3；如果x,y屬于相同的分部，則d(x,y)=2。

引理7[13]若在2n-1 階擬平衡二部圖G=(X,Y;E)中，Hyper-Wiener 指數(shù)的不等式WW(G) ≥9n2-3n-5e(G)等號(hào)成立時(shí)，當(dāng)且僅當(dāng)G中任意兩個(gè)不相鄰的點(diǎn)x,y∈V(G)，如果x,y屬于不同的分部，則d(x,y)=3；如果x,y屬于相同的分部，則d(x,y)=2。

2 主要結(jié)果

文獻(xiàn)[11]利用簡(jiǎn)單平衡二部圖的一些度、邊數(shù)和譜半徑條件，提出了該圖是弱哈密爾頓連通的充分條件。本文在此基礎(chǔ)上優(yōu)化了引理2和引理3，并且利用平衡二部圖是弱哈密爾頓-連通的邊充分條件來推出了擬平衡二部圖是弱逐點(diǎn)可跡的邊充分條件，然后根據(jù)譜半徑及無符號(hào)拉普拉斯譜半徑給出了擬平衡二部圖是弱逐點(diǎn)可跡的充分條件，最后利用拓?fù)渲笖?shù)給出了擬平衡二部圖是弱逐點(diǎn)可跡的充分條件。

下面介紹定理中需要用到的三類特殊圖。

（i）CP是由的每個(gè)頂點(diǎn)上刪除t-1條邊所構(gòu)成，此時(shí)t=k+1或t=n-k。通過計(jì)算可得e(CP)=n2-tn+n+t2-t=n(n-k) +k(k+1)。

（ii）DP是由CP刪去點(diǎn)v以及與v相鄰邊所構(gòu)成的圖，其中v是CP與X中的每個(gè)頂點(diǎn)都相鄰的點(diǎn)，可得e(DP)=n(n-k)+k(k+1)-n=n(n-k-1)+k(k+1)。

注記1在2n-1階擬平衡二部圖G=(X,Y;E)中，G′是由G中分部Y添加一個(gè)點(diǎn)v，且將v與X中所有點(diǎn)相連所構(gòu)成的圖，即G′是2n階平衡二部圖，則G′是弱哈密爾頓-連通的，當(dāng)且僅當(dāng)G是從X中任一點(diǎn)出發(fā)都是可跡的。

下設(shè)t是極大整數(shù)，使得Kt,t?G，那么t≥k+1。使用反證法證明t≥n-k+1。若k+1≤t≤n-k，則設(shè)X2?X，Y2?Y且使得(X2,Y2;E2)=Kt,t，此時(shí)需要考慮兩種情形。

（1）若不存在一個(gè)點(diǎn)x∈X X2是與Y2中所有頂點(diǎn)相鄰。由的定義可知，對(duì)于G中不相鄰點(diǎn)對(duì)x，y∈Y2的度和，均有d(x)+d(y)≤n+1。因?yàn)閐(y)≥t，有x∈X X2且d(x)≤n-t+1，則

又因?yàn)閑(G)≥n(n-k)+k(k+1)，可 得n2+n+t2-(n+1)t≥n(n-k)+k(k+1)，即[t-(n-k)][t-(k+1)]≥0。下面進(jìn)行分類討論。

（i）[t-(n-k)][t-(k+1)]>0，可得tn-k，與假設(shè)矛盾。

（ii）[t-(n-k)][t-(k+1)]=0，可得t1=k+1，或t2=n-k，且公式（1）中等號(hào)均成立。此時(shí)對(duì)應(yīng)的圖為：當(dāng)t=k+1 時(shí)，G=(X,Y;E)是由Kn,n中XX2的n-k-1 個(gè)頂點(diǎn)上均刪除k條邊所構(gòu)成；當(dāng)t=n-k時(shí)，G=(X,Y;E)是由Kn,n中XX2的k個(gè)頂點(diǎn)上均刪除n-k-1條邊所構(gòu)成，即G∈CP，矛盾。

（2）若存在一點(diǎn)x∈XX2且與Y2中所有頂點(diǎn)相鄰。則對(duì)于ω∈YY2，d(ω)≤n-t+1。否則，若存在一個(gè)頂點(diǎn)ω∈YY2，使得d(ω)≥n-t+2，因?yàn)閷?duì)任意x2∈X2，有d(x2)≥t。根據(jù)閉包定義可知，ω與X2中每個(gè)頂點(diǎn)都相鄰有，矛盾。則

又因?yàn)閑(G)≥n(n-k)+k(k+1)，可得n2+n+t2-(n+1)t≥n(n-k)+k(k+1)，即[t-(n-k)][t-(k+1)]≥0。下面進(jìn)行分類討論。

（i）[t-(n-k)][t-(k+1)]>0，可得tn-k，與假設(shè)矛盾。

（ii）[t-(n-k)][t-(k+1)]=0，可得t1=k+1，t2=n-k，且公式（2）中等號(hào)均成立。這時(shí)對(duì)應(yīng)的圖為：當(dāng)t=k+1時(shí)，G=(X,Y;E)是由Kn,n中YY2的n-k-1個(gè)頂點(diǎn)上均刪除k條邊所構(gòu)成；當(dāng)t=n-k時(shí)，G=(X,Y;E)是由Kn,n中YY2的k個(gè)頂點(diǎn)上均刪除n-k-1條邊所構(gòu)成，即G∈CP，矛盾。

由公式（1）和公式（2）兩種情形可知，t≥n-k+1。

則有n2-kn+k2+1≥e(G)≥n(n-k)+k(k+1)，得k≤1。與k≥2矛盾，故s+t≥2n-k+1。

最后進(jìn)一步利用反證法來證明。如果δ(G)≥k，那么Kn,n-k+1?G，除非G∈CP。假設(shè)G?CP，且Kn,n-k+1?G。設(shè)X4?X，Y4?Y使得(X4,Y4;E4)=Ks,t，s+t≥2n-k+1，且XX4與YY4均為非空集合。對(duì)于x∈X4、y∈Y4，根據(jù)δ(G)≥k與閉包定義可得d(x)≤n-k+1 和d(y)≤n-k+1，而此時(shí)d(x) +d(y)≥s+t≥2n-k+1，得出k≤1。若k=1 時(shí)，s+t=2n-k+1=2n，此時(shí)Kn,n-k+1=G，矛盾，否則k≤0，矛盾。因此，若δ(G)≥k，那么Kn,n-k+1?G，除非G∈CP。證明完畢。

定理2在2n階的平衡二部圖G=(X,Y;E)中如果δ(G)≥k≥1，n≥2k+2，e(G)≥n(n-k)+k(k+1)，則G是弱哈密爾頓-連通的，除非G∈CP。

證明若G?CP，由定理1可得Kn,n-k+1?G。

定理3在2n-1 階擬平衡二部圖G=(X,Y;E)中=n-1。如果δ(G)≥k≥1，n≥2k+2，e(G)≥n(n-k-1)+k(k+1)，則G從X中任一點(diǎn)出發(fā)都是可跡的，即G是弱逐點(diǎn)可跡圖，除非G∈DP。

證明若G?DP，在G中添加一個(gè)新的頂點(diǎn)v，使其與X中的每個(gè)頂點(diǎn)都相鄰，且不與Y中的任意一點(diǎn)相鄰，所得到的圖為G′。由定理?xiàng)l件可知e(G)≥n(n-k)+k(k+1)-n，e(G′)≥n(n-k)+k(k+1)。由定理2可知，G′是弱哈密爾頓-連通的；由注1可知，G從X中任一點(diǎn)出發(fā)都是可跡的，即G是弱逐點(diǎn)可跡圖。證明完畢。

定理4在2n-1階擬平衡二部圖G=(X,Y;E)中

（1）若n≥k(k+1)，μ(G)≥μ(DP)，則G是弱逐點(diǎn)可跡圖，除非G∈DP。

（2）若n≥k(k+1)，q(G)≥q(DP)，則G是弱逐點(diǎn)可跡圖，除非G∈DP。

證明（1）通過注2 和引理4 可知那么e(G)≥n(n-k)≥n(n-k-1)+k(k+1)，其中n≥k(k+1)。通過定理3可知，G是弱逐點(diǎn)可跡圖，除非G∈DP。

定理5若n≥2k+2，則有

證明注意到e(DP)=n(n-k-1)+k(k+1)，以及DP滿足引理6-8 的等式成立條件。再由引理6-8可以得出

定理6在2n-1 階擬平衡二部圖G=(X,Y;E)中，δ(G)≥k≥1，n≥2k+2。若W(G)≤3n2-5n+2kn-2k2-2k+2，則圖G是弱逐點(diǎn)可跡的，除非G∈DP。

證明假設(shè)G?DP且G不是弱逐點(diǎn)可跡的，由定理3 可知，e(G)

類似地，對(duì)于任意的i(2 ≤i≤n)和任意的j(1≤j≤n-1)，有

根據(jù)W(G)的定義，有

與定理?xiàng)l件W(G)≤3n2-5n+2kn-2k2-2k+2矛盾。證明完畢。

定理7在2n-1 階擬平衡二部圖G=(X,Y;E)中，δ(G)≥k≥1，n≥2k+2。若WW(G)≤4n2+5kn-7n-5k2-5k+3，則圖G是弱逐點(diǎn)可跡的，除非G∈DP。

證明假設(shè)G?DP且圖G不是弱逐點(diǎn)可跡的，由定理3可知，e(G)

已知對(duì)于任意的i(1≤i≤n)和j(1≤j≤n-1)，有

根據(jù)WW(G)的定義，有

與定理?xiàng)l件WW(G)≤4n2+5kn-7n-5k2-5k+3矛盾。證明完畢。

證明假設(shè)G?DP且圖G不是弱逐點(diǎn)可跡的，由定理3可知，e(G)

對(duì)于任意的i(1≤i≤n)和j(1≤j≤n-1)，有

根據(jù)H(G)的定義，有

3 結(jié)論

本文研究了擬平衡二部圖的弱逐點(diǎn)可跡性，主要利用圖的閉包來解決。首先在n≥2k+2，k≥1的條件下優(yōu)化了平衡二部圖弱哈密爾頓-連通圖的邊充分條件；其次根據(jù)平衡二部圖是弱哈密爾頓-連通的邊充分條件來得到擬平衡二部圖是弱逐點(diǎn)可跡的邊充分條件；最后利用圖的譜和指數(shù)刻畫了擬平衡二部圖的弱逐點(diǎn)可跡性，本文為研究擬平衡二部圖的結(jié)構(gòu)性質(zhì)提供了一種行之有效的方法。