廣義太陽(yáng)圖與路的笛卡兒積圖的任意可分性?

西日尼阿依·努爾麥麥提，張盼盼，劉鳳霞，孟吉翔

(新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆 烏魯木齊 830046)

0 引言

設(shè)G=(V,E)是個(gè)簡(jiǎn)單的，無(wú)向的，n個(gè)頂點(diǎn)的圖.如果序列τ=(n1,n2,…,nk)滿足n=，則稱序列τ在圖G中是可允許的.如果τ=(n1,n2,…,nk)是圖G的可允許序列且存在頂點(diǎn)集V(G)的一個(gè)劃分(V1,V2,…,Vk)，滿足|Vi|=ni對(duì)于所有的1 ≤i ≤k成立，且Vi導(dǎo)出的子圖G[Vi]是連通的，則稱這個(gè)可允許的序列τ是可實(shí)現(xiàn)的，并且稱圖G是τ-可分的.如果圖G的每個(gè)可允許序列在圖G中可實(shí)現(xiàn)，則我們把圖G稱為任意可分圖（簡(jiǎn)稱為AP圖或AVD圖）.如果圖G對(duì)于每個(gè)至多是k部分的劃分τ都是τ-可分的,則稱這個(gè)圖G是k-可分的.如果一個(gè)圖是2-可分的，則這個(gè)圖的性質(zhì)跟限制連通性是有關(guān)的，有關(guān)限制連通性的研究見文獻(xiàn)[1,2].

兩個(gè)圖G和H的笛卡兒積記為G□H，其頂點(diǎn)集為V(G)×V(H)，G□H的兩個(gè)頂點(diǎn)(v1,u1)，(v2,u2)相鄰當(dāng)且僅當(dāng)v1=v2且u1u2∈E(H)或者u1=u2且v1v2∈E(G).

如果圖G含有一條哈密爾頓路，則此圖稱為可跡圖.路和可跡圖G都是任意可分的.Baudon[3]等人提出了猜想任意可分圖G和可跡圖H的笛卡兒積圖是任意可分的，并且他們證明了圖H是頂點(diǎn)數(shù)至多為4的可跡圖時(shí)猜想成立.眾所周知，如果兩個(gè)圖G和H都是可跡圖，則它們的笛卡兒積也是可跡圖.Liu[4]等人證明了T是最大度至多為n+1的樹，如果樹T中有一條包含T中所有度為n+1的頂點(diǎn)的路，則T□Cn是任意可分圖.

與經(jīng)典問題完美匹配結(jié)合是任意可分圖的重要研究方向.若一個(gè)圖G是任意可分圖，則可允許序列(2,2,…,2)或(1,2,2,…,2)一定是可實(shí)現(xiàn)的，即G有完美匹配或幾乎完美匹配.從而一個(gè)圖含有完美匹配或幾乎完美匹配的必要條件是一個(gè)圖是任意可分圖.Liu[5]等人證明了團(tuán)數(shù)為2的2K2-free圖是任意可分圖當(dāng)且僅當(dāng)此圖含有完美匹配或幾乎完美匹配.Horňák[6]等人證明了對(duì)于一個(gè)頂點(diǎn)數(shù)至少為20的連通圖G，如果圖G有完美匹配或幾乎完美匹配，并且任意兩個(gè)不相鄰的頂點(diǎn)度數(shù)之和至少為n?5，則圖G是任意可分的.

如果圖G有任意可分的生成子圖，則此圖是任意可分圖，而樹是最簡(jiǎn)單的生成子圖.因此，自從2002年提出任意可分圖的定義后，在過去的幾年里有很多有關(guān)任意可分樹的結(jié)論.Horňák和Wo′zniak[7]證明了任意可分樹的最大度至多為6，并且提出了猜想如果樹T的最大度至少為5，則T不是任意可分的.此猜想被Barth和Fournier[8]證明了，且他們證明了一個(gè)任意可分樹T的最大度至多為4，并且每個(gè)4-度點(diǎn)與一個(gè)葉子點(diǎn)相鄰.Cichacz[9]等人完全刻畫了四個(gè)葉子點(diǎn)的任意可分毛毛蟲圖.

星型樹S(a1,a2,…,at,b1,b2,…,bs)（簡(jiǎn)記為S）是一個(gè)同態(tài)于星K1,k的樹.K1,k的每一條邊分別被長(zhǎng)度為a1,a2,…,at,b1,b2,…,bs的路替換而得的圖，其中ai(1 ≤i ≤t)是奇數(shù)，bl(1 ≤l ≤s)是偶數(shù)，且Δ(S)=k=t+s ≥2.

廣義太陽(yáng)圖是一個(gè)圈Cn上的某些頂點(diǎn)懸掛星型樹的單圈圖.圈Cn上的頂點(diǎn)稱為中心點(diǎn)，用u1,u2,…,un來(lái)表示.我們用S??=S(n;k1,k2,…,kn)來(lái)記d(ui)≥4(1 ≤i ≤n)，且S(n;k1,k2,…,kn)?E(Cn)=S1∪S2∪…∪Sn是廣義太陽(yáng)圖，其中Si=S(a1i,a2i,…,ati,b1i,b2i,…,bsi)是Δ(Si)=ki=ti+si≥2(1 ≤i ≤n)的星型樹，且Δ(S??)=（如圖1）.

圖1 廣義太陽(yáng)圖S??Fig 1 Generalized Sun-like graph S??

在這篇文章中，我們主要研究廣義太陽(yáng)圖和路的笛卡兒積的任意可分性.首先按m的奇偶性分類，給出了G??=S??□Pm是任意可分圖的一些充分條件，然后結(jié)合Tutte’s定理，給出了G??=S??□Pm不是任意可分圖的一些充分條件.

1 S??□Pm的任意可分性

圖3 圖S(5;4,3,4,4,3)的拷貝分Fig 3 The copies of graph S(5;4,3,4,4,3)

2 結(jié)論

文中我們給出了圖G??=S??□Pm是可跡圖，且是任意可分圖的充分條件.并且結(jié)合Tutte’s定理給出了圖G??=S??□Pm不是任意可分圖的充分條件.