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

张子凡; 杨卫华

doi:10.13568/j.cnki.651094.651316.2023.12.10.0001

您当前的位置：

首页 >

文章列表页 >

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

数理科学 | 更新时间：2026-01-21

- 一类笛卡儿积图中完美匹配扩充为哈密顿圈
- 一类笛卡儿积图中完美匹配扩充为哈密顿圈
- 新疆大学学报（自然科学版中英文） 2024年41卷第2期页码：209-217
- 作者机构：
  
  太原理工大学数学学院
- 作者简介：
- 基金信息：
  
  国家自然科学基金“连通性条件下图的长圈结构若干问题研究”（12371356）
- DOI：10.13568/j.cnki.651094.651316.2023.12.10.0001
  中图分类号： O157.5
- 纸质出版：2024
- 稿件说明：
移动端阅览
[1]张子凡,杨卫华.一类笛卡儿积图中完美匹配扩充为哈密顿圈[J].新疆大学学报(自然科学版)(中英文),2024,41(02):209-217.
[1]张子凡,杨卫华.一类笛卡儿积图中完美匹配扩充为哈密顿圈[J].新疆大学学报(自然科学版)(中英文),2024,41(02):209-217. DOI： 10.13568/j.cnki.651094.651316.2023.12.10.0001.

DOI：10.13568/j.cnki.651094.651316.2023.12.10.0001.

摘要

令Q3□Cq=Q~1Q2…Qq为三维超立方体与圈的笛卡儿积图

Qi(1≤i≤q)同构于Q3

M为Q3□Cq的完美匹配.依据每个Q3中是否有点被连接两个Q3的M中边饱和

把Q3□Cq表示成block1和block2交替出现的序列.研究了Q3□Cq中完美匹配M扩充为哈密顿圈的充分条件

证明了以下结论:q≤1

S={Q1

…

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.

Abstract

Let Q3□Cq=Q~1Q2…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 blockl and block2alternating 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

…

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 blockl 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).

关键词

Keywords

references

CAHA R,KOUBEK V.Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets[J].Journal of Graph Theory,2006,51(2):137-169.

DVORAK T.Hamiltonian cycles with prescribed edges in hypercubes[J].SIAM Journal on Discrete Mathematics,2005,19(1):135-144.

DIMITROV D,DVORAK T,GREGOR P,et al.Gray codes avoiding matchings[J].Discrete Mathematics&Theoretical Computer Science,2009,11(2):123-147.

LIU J J,WANG Y L.Hamiltonian cycles in hypercubes with faulty edges[J].Information Sciences,2014,256:225-233.

RUSKEY F,SAVAGE C.Hamilton cycles that extend transposition matchings in Cayley graphs of Sn[J].SIAM Journal on Discrete Mathematics,1993,6(1):152-166.

ZULKOSKI E,GANESH V,CZARNECKI K.MathCheck:A math assistant via a combination of computer algebra systems and SAT solvers[C]//FELTYA P,MIDDELDORP A.International Conference on Automated Deduction.Cham:Springer,2015:607-622.

WANG F,ZHAO W S.Matchings extend to Hamiltonian cycles in 5-cube[J].Discussiones Mathematicae Graph Theory,2018,38(1):217-231.

CHEN Y C,LI K L.Matchings extend to perfect matchings on hypercube networks[C]//Proceedings of the International MultiConference of Engineers and Computer Scientists,Hong Kong:IMECS,2010.

WANG F,ZHANG H P.Small matchings extend to Hamiltonian cycles in hypercubes[J].Graphs and Combinatorics,2016,32(1):363-376.

DVOˇRAK T,FINK J.Gray codes extending quadratic matchings[J].Journal of Graph Theory,2019,90(2):123-136.

KREWERAS G.Matchings and Hamiltonian cycles on hypercubes[J].Bulletin of the Institute of Combinatorics and Its Applications,1996,16:87-91.

FINK J.Perfect matchings extend to Hamilton cycles in hypercubes[J].Journal of Combinatorial Theory,Series B,2007,97(6):1074-1076.

ALAHMADI A,ALDRED R E L,ALKENANI A,et al.Extending a perfect matching to a Hamiltonian cycle[J].Discrete Mathematics&Theoretical Computer Science,2015,17(1):241-254.

GAUCI J B,ZERAFA J P.Perfect matchings and hamiltonicity in the Cartesian product of cycles[J].Annals of Combinatorics,2021,25(3):789-796.

GAUCI J B,ZERAFA J P.Accordion graphs:Hamiltonicity,matchings and isomorphism with quartic circulants[J].Discrete Applied Mathematics,2022,321:126-137.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

具有强互反性的双圈图的刻画(英文)

偶匹配可扩图的度和连通度条件(英文)

关于全图补图的完美匹配(英文)

六角系统中完美匹配的覆盖与对应(英文)

一类苯系统的克拉公式