连通的顶点可迁图的色唯一性

本文给出从一个已知的顶点可迁的非色唯一图出发,构造无穷多个顶点可迁的非色唯一图的一种方法,据此给出若干类无穷多个连通的顶点可迁,但不是色唯一的图簇,从而进一步否定地回答了Chia在[1]中提出的问题.

几类非色唯一的连通顶点可迁图

给出了几类非色唯一的连通顶点可迁图,即kKq kKq(k≥2,q≥2)、kCn kCn(k≥2,n≥3)和kRn kRn(k≥2,n∈{3,4,6,12}),其中Kq是具有q个顶点的完全图,Cn是具有n个顶点的回路,Rn是具有n个顶点的最大正则平面图,是两个不相交图的Zykov乘积运算。

非色唯一的连通顶点可迁图的广泛存在性

本文中,我们构造性地证明了:对应于每一个给定的色唯一的连通顶点可迁图,均存在着无穷多个与之对应的非色唯一的连通顶点可迁图.据此,我们部分地回答了G.L.Chia在[4]中提出的第二个问题.

拟顶点可迁图上简单随机游走的切割点

证明了体积增长不低于5次多项式的拟顶点可迁图上的简单随机游走几乎处处有无穷多个切割时,从而有无穷多个切割点.该结论在所论情形下肯定了Benjamini,Gurel-Gurevich和Schramm在文[2011,Cutpoints and resistance of random walk paths,Ann.Probab.,39(3):1122-1136]中提出的猜想:顶点可迁图上暂留简单随机游走几乎处处有无穷多个切割点.

关于L.Lovase猜想

本文证明了旋转型的顶点可迁连通图有Harmilton路,从而验证了L.Lovasz猜想在此条件下的正确性。