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

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

0 引言

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

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

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

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

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

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

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

圖1 廣義太陽圖S??Fig 1 Generalized Sun-like graph S??

在這篇文章中，我們主要研究廣義太陽圖和路的笛卡兒積的任意可分性.首先按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不是任意可分圖的充分條件.