维数不超过7的超立方体三次幂的可区别数  

On distinguishing number of cube of n(≤7)-dimensional hypercube

作　　者：高志军[1] 李懿[1] 何鸣[1] 

机构地区：[1]黑龙江科技学院计算机与信息工程学院,哈尔滨150027

出　　处：《黑龙江科技学院学报》2008年第1期61-64,80,共5页Journal of Heilongjiang Institute of Science and Technology

摘　　要：根据n维超立方体Hn及其p次幂Hpn的结构特性,结合其顶点间距离与海明距离关系来确定其顶点坐标的性质,采用"脊"的技术和顶点着色的方法,对维数不超过7的超立方体三次幂的可区别数进行了研究。通过适当地选取顶点得到了H33的可区别数为8,H34的可区别数为5,H36和H37的可区别数都为2,及H35可区别数的一个上界为3。According to the structural properties of the n-dimensional hypercube graph Hn and its p powers Hn^p, combined with the relations between the distance and hamming distance between its vertices, to determine the properties of the vertex coordinate, and applying the methods of the ＂ spine＂ technology and vertices coloring, this paper studies the distinguishing number of the cube of the n（ ≤7）- dimensional hypercube, offers the distinguishing number of graph H3^3, H4^3, H6^3 and H7^3 is 5,8,2 and 2, obtained respectively, and concludes that the upper boundary of the distinguishing number of graph H5^3 is 3 by selecting vertices properly.

关 键 词：图论 可区别数 超立方体 图着色 

分 类 号：O157.6[理学—数学]