劉 彬，鄧梓健，杜輕松，火博豐，b，李發(fā)旭

（青海師范大學 a. 數(shù)學與統(tǒng)計學院，b. 青海省物聯(lián)網(wǎng)重點實驗室，c. 計算機學院，d. 藏文信息處理實驗室，青海 西寧 810008）

0 引言

1935 年，Whitney［1］首次提出了擬陣的概念。為了研究擬陣中圈的性質，李萍［2］提出了擬陣圈圖的概念，并且得出了擬陣圈圖的哈密頓性［3-6］連通度［7］和路的性質［8］。對于一階圈圖的哈密頓性，已經(jīng)有了一般性的結果，并知道了連通擬陣M的圈圖的連通度［7］至少是2|E-B|- 2，其中B是M的一個基，至少含有4 個圈的連通擬陣的圈圖是一致哈密頓的［4］。本文在擬陣一階圈圖的基礎上，探究了在某些條件下均勻擬陣二階圈圖的哈密頓性。

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

(Ι1)?∈?。

(Ι2)若I∈? 且I′ ??，則I′ ∈?。

(Ι3)若I1,I2∈? 且|I1|< |I2|，則存在e∈I2-I1使得I1?e∈?。

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

定 義2［10］設n≥m≥ 0 為 兩 個 整數(shù)，E是一個n- 元集。令? = {X?E:|X| ≤m}，則(E,?)是個擬陣,這種擬陣稱為均勻擬陣，記作Um,n。

定義3［2］設擬陣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［11］設G是一個圖，包含圖G的每個頂點的路稱為圖G的一條哈密頓路；包含圖G的每個頂點的圈稱為圖G的一個哈密頓圈；如果圖G存在一個哈密頓圈，則稱之為哈密頓的。如果圖G中的每對頂點u,v都存在一條u到v的哈密頓路，則稱圖G是哈密頓連通的。如果對于圖G的任意一條邊，G都有一個包含這條邊的哈密頓圈，則稱G是正哈密頓的；如果對于圖G的任意一條邊，G都有一個不包含這條邊的哈密頓圈，則稱G是負哈密頓的。如果G既是正哈密頓的，又是負哈密頓的，則稱G是一致哈密頓的。

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

1 預備知識

引理1［11］設G是一個n- 階圖，其中n≥ 3。如果G的每個頂點v都有那么G是哈密頓的。

引理2［11］設G是一個n- 階圖，其中n≥ 3。如果G的每個頂點v都有那么G是哈密頓連通的。

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

所以，當|E|=n時，與{xi1,xi2,…,xim+1}相鄰的點的個數(shù)為

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

證 明設V(G)= {1,2,…,n}，E(G)= {eij|i≠j,且i,j∈[1,2,…,n] }。任 取i,j∈V(G)，因為G中任意兩點都相鄰，所以G中存在從i到j的哈密頓路為所以G是哈密頓連通的。任取eij∈E(G)，其中i≠j，因為G中任意兩點都相鄰，所以G中存在包含eij的哈密頓圈為：1 →2 →…→i →j →…→n →1，因 此G 是正哈密頓的。任取eij∈E(G)，存 在eik,ekj∈E(G)，其 中i≠j≠k，則G中存在不包含eij 的哈密頓圈為：1 →2 →…→i→k→j→…→n→1，因此G是負哈密頓的。故G是一致哈密頓的。

2 主要結論

定理1U2,4,U3,5,U3,6的二階圈圖是哈密頓連通的，并且是一致哈密頓的。

證明由引理6 知，U2,4的二階圈圖中每個頂點的度都是3，共有4 個頂點。U3,5的二階圈圖中每個頂點的度都是4，共有5 個頂點。U3,6的二階圈圖中每個頂點的度都是14，共有15 個頂點。故U2,4,U3,5,U3,6的二階圈圖是完全圖。又由引理7 知U2,4,U3,5,U3,6的二階圈圖是哈密頓連通的，并且是一致哈密頓的。

定理2當n=m+ 2,m+ 3,…,2m- 1,2m時，Um,n的二階圈圖是哈密頓連通的，并且是一致哈密頓的。

所以Um,2m的二階圈圖是完全圖，由引理7 可知Um,2m的二階圈圖是哈密頓連通的，并且是一致哈密頓的。綜上所述，當n=m+ 2,m+ 3,…,2m- 1,2m時，Um,n的二階圈圖是哈密頓連通的，并且是一致哈密頓的。

例1 均勻擬陣Um-1,2m的二階圈圖是哈密頓的并且是哈密頓連通的，其中m≥ 4。

下面我們提出一個猜想。

猜想1均勻擬陣Um,n的二階圈圖是哈密頓的并且是哈密頓連通的，其中m,n均為正整數(shù)，且m≥ 2,n≥m+ 2。