令Q3□Cq=Q1Q2…Qq为三维超立方体与圈的笛卡儿积图,Qi(1 ≤ I ≤ q)同构于Q3,M为Q3□Cq的完美匹配.依据每个Q3中是否有点被连接两个Q3的M中边饱和,把Q3□Cq表示成block1和block2交替出现的序列.研究了Q3□Cq中完美匹配M扩充为哈密顿圈的充分条件,证明了以下结论:q≥1,S={Q1,Q2,…,Qq},如果满足下列条件之一,则M可以扩充为哈密顿圈:(1)M中边均在Q3中;(2)任意Qi∈S中都存在点被M(Qi-1,Qi)或M(Qi,Qi+1)饱和;(3)Q3□Cq中至少各存在一个block1和block2,且每个block2中第一个Qi与最后一个Qj分别被M(Qi,Qi+1)与M(Qj-1,Qj)饱和的点的数量均为2.
Perfect Matchings Extendibility in Cartesian Product of 3-Dimensional Hypercube and Cycle
Let Q3□Cq=Q1Q2 …Qq be the Cartesian product of 3-dimensional hypercube and circle and M be a perfect matching of Q3□Cq,Qi in Q3□Cq is isomorphic to Q3.Q3□Cq can be divided into block1 and block2 alternating sequences according to whether Qi is somewhat covered by M(Qi-1,Qi)or M(Qi,Qi+1).This paper mainly studies the sufficient conditions for extending the perfect matching M of Q3口Cq to a Hamiltonian cycle,and proves the following conclusions:q ≥ 1,S={Q1,Q2,…,Qq},if one of the following conditions is true,M can be extended to a Hamiltonian cycle:(1)every edge in M joins two vertices in the same canonical Q3;(2)for any Qi ∈ S,there are vertices that are covered by M(Qi-1,Qi)or M(Qi,Qi+1);(3)Q3□Cq contains at least one block1 and one block2,and in every block2,two vertices in the first canonical Qi are covered by M(Qi,Qi+1)and two vertices in the last canonical Qj are covered by M(Qj-1,Qj).
万方数据
维普
