摘要
令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.
关键词
哈密顿圈 /
完美匹配 /
笛卡儿积图
中图分类号
O157.5
张子凡, 杨卫华.
一类笛卡儿积图中完美匹配扩充为哈密顿圈. 新疆大学学报（自然科学版中英文）. 2024, 41(02): 209-217 https://doi.org/10.13568/j.cnki.651094.651316.2023.12.10.0001
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
基金
国家自然科学基金“连通性条件下图的长圈结构若干问题研究”（12371356）
AI Summary
