一類可圖擬陣的二階圈圖的哈密頓性

李亞寧，劉彬，鄧梓健，王麗煊，火博豐，2，尹君

（1.青海師范大學數學與統計學院，青海 西寧 810008；2.青海省物聯網重點實驗室，青海 西寧 810008）

0 引言

擬陣的概念最早是由Whitney［1］在1935年提出的。它是矩陣的向量空間和圖的圈空間及鍵空間的推廣。1942年Rado［2］提出了有關擬陣的一些性質，Tutte［3-7］發展了這一概念，并研究了擬陣和圖的性質以及擬陣的連通性等問題。1972年Holzmann和Haray［8］研究并證明了擬陣基圖的一致哈密頓性。Alspach等［9］研究得到了擬陣基圖中路和圈的性質，并證明了簡單擬陣的基圖是哈密頓連通的邊泛圈圖。在此之后鄧漢元和李榮珩［10］與夏方禮［11］先后研究了擬陣基圖的1-哈密頓性與P3-哈密頓性，進一步證明基之間的關系。一個擬陣的基圖能夠反映該擬陣的不同基之間的變換關系。因此，研究擬陣的基圖有助于更好了解擬陣的性質。為了研究連通擬陣中圈的性質，李萍［12］提出擬陣圈圖的概念，得出了擬陣圈圖的哈密頓性［13-16］、連通度［17］和圈圖中圈和路的性質［18］，并把圈圖的概念推廣為n階圈圖，從而得到了n階圈圖的一些性質。對于一階圈圖的哈密頓性，已經有了一般性的結果：設G=G(M)是一個連通擬陣M的圈圖，而且B是M的一個基，則G的連通度［7］κ(G)≥2|E-B|-2。設G=G(M)是一個連通擬陣M的圈圖，而且G的最小度是δ(G)，則G的邊連通度κ′(G)=δ(G)。設G=G(M)是一個連通擬陣M的圈圖，而且M含有至少4個圈，則G是一致哈密頓的［14］。為研究一般連通擬陣的二階圈圖的哈密頓性，本文在擬陣的一階圈圖已有結果基礎上，探究了完全二部圖K2，n和K3，n的圈擬陣的二階圈圖的哈密頓性。

1 基礎知識

定義1［19-20］一個擬陣M是一個有序對(E，?)，其中E是有限集合，??2E是E中子集的集合，滿足以下的公理：

（I2）若I∈?，及I?I′，則I′∈?；

（I3）若I1，I2∈?，且|I1|＞|I2|，則存在e∈I2-I1使得I1∪e∈?。

集合?中的獨立元素成為擬陣M的獨立集。設M(E，?)是一個擬陣，若子集X??，則令X稱為M的一個相關集。極小的相關集為極小圈。令C(M)表示由擬陣M的全體極小圈組成的集合。

定義2［19］對于擬陣M，如果存在某個圖G，使得擬陣M同構于圖G的圈擬陣，那么稱M為可圖擬陣。

定義3［12］設擬陣M圈圖為G，其中頂點集V(G)=C，邊集E(G)={CC′|C，C′∈C，|C∩C′|≠0}，這里C和C′既代表G的頂點，也代表擬陣M的圈。設擬陣M的二階圈圖為G，其中頂點集V(G)=C，邊集E(G)={CC′|C，C′∈C，|C∩C′|≥2}，這里C和C′既代表G的頂點，也代表擬陣M的圈。

定義4［21］設G是一個圖，如果V(G)可以被劃分為集合U和W，使得uw是G的邊當且僅當u∈U且w∈W，則稱圖G為完全二部圖。如果|U|=s且|W|=t，那么這個完全二部圖有（s+t）個頂點和st條邊且可以由Ks，t（或Kt，s）表示。

定義5［20］設G是一個圖，包含圖G的每個頂點的路稱為圖G的一條哈密頓路；包含圖G的每個頂點的圈稱為圖G的一個哈密頓圈；如果圖G存在一個哈密頓圈，則稱之為哈密頓的。如果圖G中的每對頂點u，v都存在一條u到v的哈密頓路，則稱圖G是哈密頓連通的。

定義6［20］對于任意的整數k，且滿足3≤k≤n，圖G的每對頂點含有長度為k的圈，那么圖G就是泛圈圖。

定義7［22］設G是一個圖，如果G中的任意兩個頂點都相鄰，則稱G是完全圖。

定義8［23］設G是一個圖，如果對于所有v∈V(G)，有d(v)=k，則圖G是k-正則圖。

引理1［24］設G是n(n≥3)階簡單圖，w是最小度的頂點，如果則G是哈密頓的。

引理2(Menger定理)［21］G是一個頂點數≥k+1的圖，圖G是k-連通的當且僅當圖中任意兩個不同的頂點都被至少k條內部不相交的路連接。

2 主要定理

定理1完全二部圖K2，n(n≥2)的圈擬陣的一階和二階圈圖相同，是一個個頂點的(2n-4)-正則圖，并且連通度是(2n-4)。

證明顯然，在完全二部圖K2，n中的圈，是個數恰好等于在這n個點中取兩個點的組合數的4-圈，且如果圈與圈之間存在公共邊，則公共邊的數目為2，因此K2，n(n≥2)的圈擬陣的一階和二階圈圖是具有個頂點的相同的圖。

將K2，n中有兩個點的分部中的兩個點分別設為O和O′，另一分部中的n個點分別設為1，2，…，n。將經過O，i，O′，j四點的圈標記為{i，j}。則二階圈圖的頂點集合為V(C2(K2，n))={{i，j}|i，j=1，2，…，n，i≠j}。二階圈圖中任何兩點{i，j}與{k，l}相鄰當且僅當|{i，j}∩{k，l}|=1。對于其中任意一個頂點{i，j}它的鄰點為{i，s}，s≠i，j；{j，t}，t≠i，j；s，t∈{1，2，…，n}，共[ ]2(n-2)個。因此完全二部圖K2，n(n≥2)的圈擬陣的二階圈圖是(2n-4)-正則圖。

對于二階圈圖中任何兩點{i，j}與{k，l}，如果它們不相鄰，即i，j，k，l各不相同，則有如下（2n-8）條長為3的路連接{i，j}與{k，l}：

{i，j}→{i，s}→{k，s}→{k，l}|；{i，j}→{j，s}→{l，s}→{k，l}|，s∈{1，2，…，n}，s≠i，j，k，l。另有4條長為2的路：

{i，j}→{i，k}→{k，l}|，{i，j}→{i，l}→{k，l}|，{i，j}→{j，k}→{k，l}|，{i，j}→{j，l}→{k，l}|。容易看出這些路的內部點都是各不相同的，因此得到(2n-4)條內部不交的路。

對于二階圈圖中任何相鄰兩點{i，j}與{j，k}，i，j，k各不相同，則有如下（n-3）條長為3的路連接{i，j}與{j，k}：{i，j}→{i，s}→{k，s}→{j，k}|，s∈{1，2，…，n}，s≠i，j，k。

另 有（n-3）條 長 為2的 路 連 接{i，j}與{j，k}：{i，j}→{j，s}→{j，k}|，s∈{1，2，…，n}，s≠i，j，k。一 條 長 為2的 路 連 接{i，j}與{j，k}：{i，j}→{i，k}→{j，k}。一 條 邊 即 長 為1的 路 連 接{i，j}與{j，k}：{i，j}→{j，k}。容易看出這些路的內部點都是各不相同的，因此得到(2n-4)條內部不交的路。

根據引理2得此二階圈圖的連通度為(2n-4)。

定理2完全二部圖K2，n(n≥3)的圈擬陣的二階圈圖是哈密頓的。

證明如圖1所示，K2，n對應的二階圈圖有個頂點，可表示為V(K2，n)={{i，j}|i，j=1，2，…，n，i≠j}。由擬陣圈圖的定義及以上列出的頂點發現，其子集Vi={{i，j}|j=1，2，…，n，i≠j}中任意兩個點之間都有邊相連，因此由Vi所導出的二階圈圖的子圖是完全圖，顯然，完全圖是哈密頓連通的。而i≠j時點集Vi與點集Vj有公共點{i，j}，因此很容易得到此二階圈圖的哈密頓圈。如哈密頓圈表 示 在Vi中{i，j}到{i，s}的一條哈密頓路。因此完全二部圖K2，n(n≥3)的圈擬陣的二階圈圖是哈密頓的。

圖1 完全二部圖K2，nFig.1 Complete bipartite graphs K2，n

定理3完全二部圖K2，n(n≥3)的圈擬陣的二階圈圖是泛圈的。

證明針對K2，n的情形，對n用數學歸納法證明。當n=3時，K2，n對應的二階圈圖為完全圖K3，顯然是泛圈的。假定結論對于n=4，5，…，n-1成立。因此K2，n-1的圈擬陣的二階圈圖是泛圈的。在K2，n-1的二階圈圖中可以找到包含長度從的圈。由定理1和定理2，K2，n的圈擬陣的二階圈圖有個頂點，且是哈密頓的。因此存在經過每個頂點的圈。因為K2，n是由K2，n-1增加（n-1）個頂點{1，n}，{2，n}，…，{n-1，n}得到，且K2，n的頂點{1，2，3，…，n}具有對稱性，因此只需要證明對于所有個圈頂點存在包含它的長度從到的圈。

在K2，n-1的二階圈圖基礎之上先增加一個頂點{i，n}(i=1，2，…，n-1)，可找到一個包含它的長度為的圈，以此類推，當增加到（n-2）個頂點時，可以找到包含它們的長度為的圈，而即存在長度為的圈。

綜上所述，在K2，n的圈擬陣的二階圈圖中存在長度為到的圈。即K2，n(n≥3)的圈擬陣的二階圈圖是泛圈的。

定理4完全二部圖K2，n(n≥3)的圈擬陣的二階圈圖是哈密頓連通的。

證明由定理1可得，K2，n對應的二階圈圖有個頂點，將其頂點集表示為V(K2，n)={{i，j}|i，j=1，2，…，n，i≠j}，其子集為Vi={{i，j}|j=1，2，…，n，i≠j}，在其子集中任意兩個點之間都有邊相連，因此由Vi所導出的二階圈圖的子圖是完全圖，顯然完全圖是哈密頓連通的。而i≠j時點集Vi與點Vj有公共點{i，j}，所 以 在 其 二 階 圈 圖 中 可 以 找 到{1，2}→{1，3}→…→{2，3}→{2，4}→…{n-2，n-1}→{n-1，n}的哈密頓路，從而可以發現任意兩個頂點都有哈密頓路連接，所以K2，n(n≥3)的圈擬陣的二階圈圖是哈密頓連通的。

定理5完全二部圖K3，n(n≥3)的圈擬陣的二階圈圖是哈密頓的。

證明如圖2所示，將K3，n中有三個點的分部中的三個點分別設為a，b，c，另一分部中的n個點分別設為1，2，…，n。K3，n的圈都是4-圈和6-圈，4-圈是從a，b，c和這n個點中分別取兩個點的組合，所以個數恰好等于。6-圈是將a，b，c與另一個分部中的n個點中任取三個點排列，所以個數恰好等于從n個元中任取三個元的排列數A3n。隨著圈個數的增加，頂點的最小度也在逐漸變化，利用引理證明更為復雜。

圖2 完全二部圖K3，nFig.2 Complete bipartite graphs K3，n

因此對n用數學歸納法證明。當n=3時，顯然，K3，n對應的二階圈圖是哈密頓的。假定結論對于n=4，…，n-1成立。因此K3，n-1對應的二階圈圖是哈密頓的，其二階圈圖的頂點包括了4-圈和6-圈在二階圈圖中所代表的頂點。其4-圈的個數為個，6-圈的個數為A3n-1個。在其4-圈中含(a，b)，(a，c)，(b，c)的圈分別含有另一個分部的{i，j}(i≠j且i，j=1，2，3，…，n-1)，其6-圈是在一個分部中含有(a，b，c)，另一個分部中含有{i，j，k}(i≠j≠k且i，j，k=1，2，…，n-1)。已知其對應的二階圈圖是哈密頓的，所以其4-圈 與6-圈 作 為 圈 頂 點 在 二 階 圈 圖 中 存 在 哈 密 頓 圈{i，j}→{i，j，k}→{i，j}。K3，n與K3，n-1相比，其4-圈個數增加了[ 3(n-1)]個，6-圈個數增加了[A3n-A3n-1=3(n-1)(n-2)]個。在其4-圈中含(a，b)，(a，c)，(b，c)分別增加了{1，n}，{2，n}，…，{n-1，n}的圈，且此時在新增的4-圈中，在a，b，c分部相同時，圈與圈之間有一個公共元n則有連邊；在a，b，c分部不完全相同時，圈與圈在{i，n}(i=1，2，…，n-1)中兩個元均相同時才有連邊。在其新增的4-圈中可以找到與新增的6-圈中有連邊的圈，例如4-圈(a，1，b，n)與6-圈(a，1，b，n，c，i)(i≠1，n)均有連邊。且6-圈中若在1，2，3，…，n的分部中若有兩個公共元則有連邊，即在新增的6-圈中也可以找到連邊。所以K3，n的圈擬陣的二階圈圖中存在哈密頓圈，即K3，n(n≥3)的圈擬陣的二階圈圖是哈密頓的。

定理6完全二部圖K3，n(n≥3)的圈擬陣的二階圈圖是哈密頓連通的。

證明當n=3時，顯然，K3，n對應的二階圈圖是哈密頓連通的，利用K2，n的圈擬陣的二階圈圖是K3，n的圈擬陣的二階圈圖的子圖，且在K3，n的6-圈在對應的二階圈圖中所構成的圖是完全圖的前提下而證明得出的。但發現當n≥5時，其6-圈在對應的二階圈圖中所構成的圖不是完全圖，因此對n用數學歸納法證明。假設n=4，…，n-1時結論成立，即K3，n-1的圈擬陣的二階圈圖是哈密頓連通的。在K3，n-1的4-圈中含(a，b)，(a，c)，(b，c)的圈分別含有另一個分部的{i，j}(i≠j且i，j=1，2，3，…，n-1)，將其4-圈簡記為{i，j}(i≠j且i，j=1，2，3，…，n-1)，其6-圈 是 在 一 個 分 部 中 含 有(a，b，c)，另 一 個 分 部 中 含 有{i，j，k}(i≠j≠k且i，j，k=1，2，…，n-1)，將6-圈簡記為{i，j，k}(i≠j≠k且i，j，k=1，2，…，n-1)。所以在其對應的二階圈圖中可以找到從4-圈對應的圈頂點到6-圈對應的圈頂點的哈密頓路{i，j}→{i，j，k}。

那么K3，n與K3，n-1相比，4-圈中含(a，b)，(a，c)，(b，c)的圈分別新增了{1，n}，{2，n}，…，{n-1，n}的圈，在新增的4-圈對應的圈頂點中可以找到連邊的頂點，即{1，n}→{2，n}→…→{n-1，n}。在其6-圈中新增了含有n的頂點，6-圈與6-圈在1，2，3，…，n中若有兩個公共元則有連邊，且在新增的4-圈與6-圈中若含有n以及其它公共元，則可以找到連邊，所以在K3，n的圈擬陣的二階圈圖中同樣可以找到從4-圈到6-圈的哈密頓路{i，j}→{i，j，k}，此時i≠j≠k且i，j，k=1，2，…，n。

綜上所述，K3，n的圈擬陣的二階圈圖是哈密頓連通的。

猜想1完全二部圖K2，n和K3，n的圈擬陣的二階圈圖是具有一致哈密頓性的。