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

摘要

令Q₃□C_q=Q¹Q²…Q^q为三维超立方体与圈的笛卡儿积图,Qⁱ（1≤i≤q）同构于Q₃,M为Q₃□C_q的完美匹配.依据每个Q₃中是否有点被连接两个Q₃的M中边饱和,把Q₃□C_q表示成block1和block2交替出现的序列.研究了Q₃□C_q中完美匹配M扩充为哈密顿圈的充分条件,证明了以下结论:q≤1,S={Q¹,Q²,…,Q^q},如果满足下列条件之一,则M可以扩充为哈密顿圈:（1）M中边均在Q₃中;（2）任意Qⁱ∈S中都存在点被M(Q^i-1,Qⁱ)或M(Qⁱ,Qⁱ⁺¹)饱和;（3） Q₃□C_q中至少各存在一个block1和block2,且每个block2中第一个Qⁱ与最后一个Q^j分别被M(Qⁱ,Qⁱ⁺¹)与M(Q^j-1,Q^j)饱和的点的数量均为2.

关键词

哈密顿圈 / 完美匹配 / 笛卡儿积图