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

作     者：张子凡 杨卫华 ZHANG Zifan;YANG Weihua

作者机构：太原理工大学数学学院山西晋中030600 

出 版 物：《新疆大学学报（自然科学版中英文）》 (Journal of Xinjiang University(Natural Science Edition in Chinese and English))

年 卷 期：2024年第41卷第2期

页      面：209-217页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：国家自然科学基金“连通性条件下图的长圈结构若干问题研究”(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.