论文部分内容阅读
本文主要研究了超立方体的一种结构特性——超立方体三次幂的可区别数和超立方体及其高次幂的边可区别数问题.图的可区别数是破坏图对称性的最小可区别的顶点标号数(颜色数)；图的边可区别数是破坏图对称性的最小可区别的边标号数(颜色数).
对于图的可区别数问题，Bogstad和Cowen在DiscreteMath.2004年发表的论文中研究了超立方体及其二次幂的可区别数，并提出了如下猜想：对于给定的正整数p，当n充分大时，n维超立方体p次幂的可区别数等于2.根据这个猜想本文作了如下研究.
1根据n维超立方体p次幂的结构特性，研究了其顶点间距离与海明距离的关系，给出了确定顶点坐标的充分必要条件，并结合“脊”的技术和顶点着色的方法对n维超立方体三次幂H3n的可区别数进行了研究.得到H3n可区别数的一个上界，即，当n≥6时，H3n的可区别数不超过5.
2在给出了n维超立方体三次幂H3n可区别数的一个上界的基础上，对维数不超过7的超立方体三次幂的可区别数进行了研究.通过适当地选取顶点得到了H33的可区别数为8,H34的可区别数为5，H36和H37的可区别数都为2，及H35可区别数的一个上界为3.
3提出了图的边可区别数概念.给出了n阶路Pn和n阶圈Cn的边可区别数；根据n维超立方体Hn及其p次幂Hpn的结构特性，对n维超立方体Hn，n维超立方体二次幂H2n和n维超立方体p(＞2)次幂Hpn的边可区别数进行了研究，得到了n维超立方体及其二次幂H2n的边可区别数，和n维超立方体高次幂Hpn的边可区别数的一个上界.即，当n=2时，H2的边可区别数为3；当n≥3时，Hn的边可区别数为2；当n≥6时，H2n的边可区别数为2；当n≥4,n≥p＞2时，Hpn的边可区别数小于等于3.