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

Some Families of Non-chromatically Unique Connected Vertex-Transitive Graphs

给出了几类非色唯一的连通顶点可迁图,即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乘积运算。

Some infinite families of connected vertex-transitive graphs which are not chromatically unique are given in this paper. They are kKq⊙kKq for any positive integers k≥2 and q≥2, kCn⊙kCn for any positive integers k≥2 and n≥3, and kRn⊙kRn for any positive integers k≥2 and n ∈ {3,4,6,12}, where Rn is the maximal regular-planar graph and ⊙ is the operation of two graphs given by Zykov.