具有 Hamilton 性的次序列

朱永津、刘振宏在[1]中给出了两类次序列,它们不满足 Chvátal 条件,其中一类甚至不满足 Bondy 和 Chvátal 的 n-闭包是完全图的条件,但它们却都保证了图的Hamilton 圈的存在.本文推广了[1]的结果,得到了更为广泛的两大类具有前述性质的次序列.     

一类新的具哈密顿性的次序列

在[1]中首先提出了两类不满足 Chvatal 条件的具哈密顿性的次序列,而且其中之一甚而不满足 Bondy-Chvátal 条件.[2]中又对这两类序列作了推广.这些结果都有一个特点,即次序列中的次数都只取某几个值,比较整齐.因而使人想到可否使次数更多样化一些而且仍具有类似的性质?可否得到其次数和相对小一些(尽可能小)的具类似性质的次     

Schrijver图SG(2k+2,k)的Hamilton性

通过图G的每个顶点的路称为Hamilton路,通过图G的每个顶点的圈称为Hamilton圈,具有Hamilton圈的图G称为Hamilton图.1952年Dirac曾得到关于Hamilton图一个充分条件的结论:图G有n个顶点,如果每个顶点υ满足:d(υ)≥n/2,则图G是Hamilton图.本文研究了Schrijver图SG(2k+2,k)的Hamilton性,采用寻找Hamilton圈的方法得出了Schrijver图SG(2k+2,k)是Hamilton图.     

正圆有向图中的弧不相交的Hamilton路和圈

2012年,Bang-Jensen和Huang(J.Combin.Theory Ser.B.2012,102:701-714)证明了2-弧强的局部半完全有向图可以分解为两个弧不相交的强连通生成子图当且仅当D不是偶圈的二次幂,并提出了任意3-强的局部竞赛图中包含两个弧不相交的Hamilton圈的猜想.主要研究正圆有向图中的弧不相交的Hamilton路和Hamilton圈,并证明了任意3-弧强的正圆有向图中包含两个弧不相交的Hamilton圈和任意4-弧强的正圆有向图中包含一个Hamilton圈和两个Hamilton路,使得它们两两弧不相交.由于任意圆有向图一定是正圆有向图,所得结论可以推广到圆有向图中.又由于圆有向图是局部竞赛图的子图类,因此所得结论说明对局部竞赛图的子图类――圆有向图,Bang-Jensen和Huang的猜想成立.     

The traveling salesman problem: a book review

We review the recent book authored by David L. Applegate, Robert E. Bixby, Vasěk Chvátal and William J. Cook, The traveling salesman problem: a computational study, Princeton Series in Applied Mathematics. Princeton University Press 2007, Hardback price $45.00 / ￡26.95, 606pp, ISBN 978-0-691-12993-8.      

3-连通3-正则图中的可序子集

图G的k元点集X={x1,x2,…,xk}被称为G的k-可序子集,如果X的任意排列都按序排在G的某个圈上.称G是k-可序图,如果G的每一个k元子集都是G的k-可序子集.称G为k-可序Hamilton图,如果X的任意排列都位于G的Hamilton圈上.研究了3-连通3-正则图的可序子集的存在性问题.     

对称群上Cayley图的DNA计算

有一类图称为Cayley图或群图.猜想每个Cayley图都是Hamilton图.求Cayley图和有向Cayley图中的Hamilton圈和路自然产生在计算科学里.这篇文章研究了对称群上Cayley图的DNA计算和给出了求它的Hamilton圈的DNA算法.     

Hamilton图的特定生成子图问题的反例

文[1]定理3断言:一个Hamilton图G必存在仅有p条桥的相间偶圈,如果相间偶圈的边中有边在G的P个不连通初等子圈上(P≥2)本文的反例表明上述结论是错的,从而[1]中关于Peterson图不是Hamilton图的证明也不成立.     

关于Hamilton3-正则2-连通平面图的一个注记

设Fk*是满足以下条件的3-正则2-连通平面图G所组成的图类,在G中存在这样的圈C,使得G-E(C)产生k个不相交的树T1,…,Tk(|E(Ti)|≥3,i=1,…,k),且这些树是按C的指定方向C*依次粘在圈C上的．本文主要证明了如下结果:Fk*中的图都是Hamilton的．     

“格子笼”图的Hamilton圈问题

对“格子笼”图的Hamilton性进行了研究,得到了判定“格子笼”图是Hamilton图的一个非常简洁的充分必要条件,从而完全解决了“格子笼”图的Hamilton性问题.