一类笛卡儿积图中完美匹配扩充为哈密顿圈  

Perfect Matchings Extendibility in Cartesian Product of 3-Dimensional Hypercube and Cycle

作　　者：张子凡 杨卫华 ZHANG Zifan;YANG Weihua(College of Mathematics,Taiyuan University of Technology,Jinzhong Shanxi 030600,China)

机构地区：[1]太原理工大学数学学院,山西晋中030600

出　　处：《新疆大学学报（自然科学版中英文）》2024年第2期209-217,共9页Journal of Xinjiang University(Natural Science Edition in Chinese and English)

基　　金：国家自然科学基金“连通性条件下图的长圈结构若干问题研究”(12371356)。

摘　　要：令Q_(3)□C_(q)=Q^(1)Q^(2)…Q^(q)为三维超立方体与圈的笛卡儿积图,Q^(i)(1≤i≤q)同构于Q_(3),M为Q_(3)□C_(q)的完美匹配.依据每个Q_(3)中是否有点被连接两个Q_(3)的M中边饱和,把Q_(3)□C_(q)表示成block1和block2交替出现的序列.研究了Q_(3)□C_(q)中完美匹配M扩充为哈密顿圈的充分条件,证明了以下结论:q≤1,S={Q^(1),Q^(2),…,Q^(q)},如果满足下列条件之一,则M可以扩充为哈密顿圈:(1)M中边均在Q_(3)中;(2)任意Q_(i)∈S中都存在点被M(Q^(i-1),Q^(i))或M(Q^(i,)Q^(i+1))饱和;(3)Q_(3)□C_(q)中至少各存在一个block1和block2,且每个block2中第一个Q^(i)与最后一个Q^(j)分别被M(Q^(i),Q^(i+1))与M(Q^(j-1),Q^(j))饱和的点的数量均为2.Let Q_(3)□C_(q)=Q^(1)Q^(2)…Q^q be the Cartesian product of 3-dimensional hypercube and circle and M be a perfect matching of Q_(3)□C_(q),Q^(i) in Q_(3)□C_(q) is isomorphic to Q_(3).Q_(3)□C_(q) can be divided into blockl and block2alternating sequences according to whether Q^(i) is somewhat covered by M(Q^(i-1),Q^(i))or M(Q^(i),Q^(i+1)).This paper mainly studies the sufficient conditions for extending the perfect matching M of Q_(3)□C_(q) to a Hamiltonian cycle,and proves the following conclusions:q≥1,S={Q^(1),Q^(2),…,Q^q},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 Q_(3);(2)for any Q^(i)∈S,there are vertices that are covered by M(Q^(i-1),Q^(i))or M(Q^(i),Q^(i+1));(3)Q_(3)□C_(q) contains at least one blockl and one block2,and in every block2,two vertices in the first canonical Q^(i) are covered by M(Q^(i),Q^(i+1))and two vertices in the last canonical Q^(j) are covered by M(Q^(j-1),Q^(j).

关 键 词：哈密顿圈 完美匹配 笛卡儿积图 

分 类 号：O157.5[理学—数学]