均勻擬陣三階圈圖的哈密頓性

吳亞平，馮麗珠

（江漢大學(xué) 人工智能學(xué)院，湖北 武漢 430056）

0 引言

擬陣的概念是由Whitney［1］在1935年和Rado［2］在1942年分別提出的，1959年，Tutte［3］發(fā)展了這一概念。二十世紀(jì)擬陣論得到了空前的發(fā)展，擬陣論為組合優(yōu)化和算法設(shè)計(jì)提供了強(qiáng)有力的工具。擬陣主要研究?jī)?nèi)容包含基圖、超平面、和圖、連通性等。2010年，李萍［4］提出了擬陣圈圖的概念，研究了擬陣圈圖的連通度、擬陣圈圖中的圈和路的性質(zhì)。文獻(xiàn)［5-9］研究了擬陣圈圖的其他性質(zhì)。2020年，劉彬等［10］研究了在某些條件下均勻擬陣二階圈圖的哈密頓性。本文將研究均勻擬陣的三階圈圖的哈密頓性。由于均勻擬陣的三階圈圖是其相應(yīng)二階圈圖的子圖，所以若均勻擬陣三階圈圖是哈密頓的，則其二階圈圖一定是哈密頓的。

關(guān)于擬陣的相關(guān)術(shù)語(yǔ)可參考文獻(xiàn)［11］。一個(gè)擬陣M是一個(gè)有序?qū)?E,?)，其中E是一個(gè)有限集合，??2E是E中子集的集合，它們滿足以下的公理：

(I1)?∈?；

(I2)若I∈? 且I′?I，則I′ ∈?；

(I3)若I1,I2∈? 且|I1|＜|I2|，則存在e∈I2-I1使得I1?e∈?。

其中，集合? 中的元素稱為擬陣M的獨(dú)立集。設(shè)M(E,?)是一個(gè)擬陣，若子集X??，則X稱為M的一個(gè)相關(guān)集。極小的相關(guān)集叫做極小圈，令C(M)表示由擬陣M的全體極小圈組成的集合。

設(shè)n≥m≥0 為兩個(gè)整數(shù)，E是個(gè)n-元集。令? ={X?E:|X|≤m}，則M(E,?)是個(gè)均勻擬陣，記作Um,n。均勻擬陣Um,n的k階圈圖為G，其中頂點(diǎn)集V(G)=C，邊集E(G)={CC′|C,C′∈C,|C?C′|≥k}。這里C和C′既代表G的頂點(diǎn)，也代表擬陣M的圈。

關(guān)于圖論的術(shù)語(yǔ)參考文獻(xiàn)［12］。設(shè)G是一個(gè)圖，包含圖G的每個(gè)頂點(diǎn)的路稱為圖G的一條哈密頓路；包含圖G的每個(gè)頂點(diǎn)的圈稱為圖G的一個(gè)哈密頓圈；如果圖G存在一個(gè)哈密頓圈，則稱之為哈密頓的。如果圖G中的每對(duì)頂點(diǎn)u,v都存在一條u到v哈密頓路，則稱圖G是哈密頓連通的。如果對(duì)于圖G的任意一條邊，G都有一個(gè)包含這條邊的哈密頓圈，則稱G是正哈密頓的；如果對(duì)于圖G的任意一條邊，G都有一個(gè)不包含這條邊的哈密頓圈，則稱G是負(fù)哈密頓的。如果G既是正哈密頓的，又是負(fù)哈密頓的，則稱G是一致哈密頓的。

設(shè)G是一個(gè)圖，如果G中的任意兩個(gè)頂點(diǎn)都相鄰，則稱G是完全圖。

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

引理1［12］設(shè)G是一個(gè)n-階圖，其中n≥3。如果G的每個(gè)頂點(diǎn)v都有那么G是哈密頓連通的。

引理2U3,n的三階圈圖共有個(gè)頂點(diǎn)，并且是正則圖，其中n≥5，且n為正整數(shù)。

證 明令E={x1,x2,…,xn}，C(U3,n)={X?E:|X|= 4}，從n個(gè) 元素中 選取4 個(gè) 元素可 以作為U3,n三階圈圖的一個(gè)頂點(diǎn)，所以U3,n的三階圈圖共有(n)4 個(gè)頂點(diǎn)。任取U3,n的三階圈圖的一個(gè) 頂 點(diǎn){xi,xj,xk,xs}，其 中i≠j≠k≠s且i,j,k,s∈{1,2,…,n}。從{xi,xj,xk,xs}中 的 任取3 個(gè)元素，剩下的一個(gè)元素需從除了xi,xj,xk,xs之外的n- 4 個(gè)元素中選擇，故與{xi,xj,xk,xs}相鄰的頂點(diǎn)有個(gè)。又由{xi,xj,xk,xs}的任意性知，U3,n的三階圈圖是正則圖。

引理3U4,n的三階圈圖共有個(gè)頂點(diǎn)，并且是正則圖，其中n≥6，且n為正整數(shù)。

證明令E={x1,x2,…,xn}，C(U4,n)={X?E:|X|= 5}，從n個(gè)元素中選取5 個(gè)元素可以作為U4,n三階圈圖的一個(gè)頂點(diǎn)，所以U4,n的三階圈圖共有個(gè)頂點(diǎn)。

采用與引理2 類似的證明，任取U4,n的三階圈圖的一個(gè)頂點(diǎn)A={xi,xj,xk,xl,xs}，其中i≠j≠k≠l≠s且i,j,k,l,s∈{1,2,…,n}。下面我們求與A相鄰的頂點(diǎn)的個(gè)數(shù)。如果A的鄰點(diǎn)與它恰好有3 個(gè)元素相同，則滿足這個(gè)條件A的鄰點(diǎn)個(gè)數(shù)為如果A的鄰點(diǎn)與它恰好有4 個(gè)元素相同，則滿足這個(gè)條件A的鄰點(diǎn)個(gè)數(shù)為

所以與A相鄰的頂點(diǎn)共有個(gè)。又由頂點(diǎn)A的任意性可知，U4,n的三階圈圖是正則。

引理4Um,n的三階圈圖共有個(gè)頂點(diǎn)，并且是正則圖，其中m,n均為正整數(shù)，且m≥3,n≥m+ 2。

證明令C(Um,n)={X?E:|X|=m+ 1}。由定義知Um,n的三階圈圖共有個(gè)頂點(diǎn)。下面證明Um,n的三階圈圖是正則圖。

同引理3 證明，任取Um,n的三階圈圖的一個(gè)頂點(diǎn)B={xi1,xi2,…,xim+1}，其中ij≠ik，j≠k，ij∈{1,2,…,n},j= 1,2,…,m+ 1。下面求與B相鄰的頂點(diǎn)的個(gè)數(shù)。如果B的鄰點(diǎn)與它恰好有k(3≤k≤m)個(gè)元素相同，則滿足這個(gè)條件B的鄰點(diǎn)個(gè)數(shù)為所以B的 鄰點(diǎn)個(gè)數(shù)由于B的任意性，可知Um,n的三階圈圖是正則圖。

引理5［10］若G是完全圖，則G是哈密頓連通的，并且是一致哈密頓的。

2 主要結(jié)論

在證明主要結(jié)論中，需要用到Pascal 公式和下面這個(gè)組合恒等式：

定理1當(dāng)m+ 2≤n≤2m- 1，m≥3，Um,n的三階圈圖是哈密頓連通的，并且是一致哈密頓的。

證明由引理4 可知，Um,n三階圈圖頂點(diǎn)數(shù)是它是正則圖。

根據(jù)式（1），有

當(dāng)m+ 2≤n≤2m- 1，可知故

可知

即當(dāng)m+ 2≤n≤2m- 1，m≥3，Um,n的三階圈圖是完全圖。由引理5 可知，Um,n的三階圈圖是哈密頓連通的，并且是一致哈密頓的。

定理2Um,2m的三階圈圖是哈密頓連通的，m≥3。

證明由引理4 可知，Um,2m三階圈圖頂點(diǎn)數(shù)是它是正則的。

首先證明一個(gè)斷言。

斷言

因此斷言成立。

根據(jù)式（1）可知，

根據(jù)斷言，則有

即

根據(jù)引理1，可知Um,2m的三階圈圖是哈密頓連通的。