The Distinguishing Number of the Crossed Cubes

摘要：

The distinguishing number of a graph G.denoted D (G),is the minimum number of colors such that there exists a coloring of the vertices of G where the group of color-preserving automorphisms of G consists only of the identity. In this paper.we compute the distinguishing number of the crossed cubes CQn, a variant of the hypercube introduced in Efe K. a variation on the hypercube with lower diameter, IEEe trans.Comput.40(1991) 1312-1316. It is shown that D (CQ1)=2; D(CQ2)=3;D(CQ3)=3; and D(CQn)=2 for n≥4.

关键词： Distinguishing number Symmetry breaking Graph coloring Crossed cubes

作者: Lei Ma Hongmei Liu Changqing Liu

作者单位: Institute of Applied Mathematics, Three Gorges University, Yichang 443002, P.R. China

会议类型: 国际会议

会议名称: The First World Congress on Global Optimization in Engineering & Science(第一届工程与科学全局优化国际会议 WCGO2009)

会议地点: 长沙

会议语种:英文

页码: 357-363

在线出版日期: 2009-06-01（万方平台首次上网日期，不代表论文的发表时间）