均匀拟阵二阶圈图的哈密顿性

刘 彬，邓梓健，杜轻松，火博丰，b，李发旭

（青海师范大学 a. 数学与统计学院，b. 青海省物联网重点实验室，c. 计算机学院，d. 藏文信息处理实验室，青海 西宁 810008）

0 引言

1935 年，Whitney［1］首次提出了拟阵的概念。为了研究拟阵中圈的性质，李萍［2］提出了拟阵圈图的概念，并且得出了拟阵圈图的哈密顿性［3-6］连通度［7］和路的性质［8］。对于一阶圈图的哈密顿性，已经有了一般性的结果，并知道了连通拟阵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 为 两 个 整数，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}相邻的点的个数为

引理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均为正整数，且m≥ 2,n≥m+ 2。