摘要
根据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.
出处
《黑龙江科技学院学报》
CAS
2008年第1期61-64,80,共5页
Journal of Heilongjiang Institute of Science and Technology
关键词
图论
可区别数
超立方体
图着色
graph theory
distinguishing number
hypercube
graph coloring
