超立方體可區(qū)別數的研究.pdf

1、本文主要研究了超立方體的一種結構特性——超立方體三次冪的可區(qū)別數和超立方體及其高次冪的邊可區(qū)別數問題.圖的可區(qū)別數是破壞圖對稱性的最小可區(qū)別的頂點標號數(顏色數)；圖的邊可區(qū)別數是破壞圖對稱性的最小可區(qū)別的邊標號數(顏色數). 對于圖的可區(qū)別數問題，Bogstad和Cowen在DiscreteMath.2004年發(fā)表的論文中研究了超立方體及其二次冪的可區(qū)別數，并提出了如下猜想：對于給定的正整數p，當n充分大時，n維超立方體p次冪

2、的可區(qū)別數等于2.根據這個猜想本文作了如下研究. 1根據n維超立方體p次冪的結構特性，研究了其頂點間距離與海明距離的關系，給出了確定頂點坐標的充分必要條件，并結合“脊”的技術和頂點著色的方法對n維超立方體三次冪H3n的可區(qū)別數進行了研究.得到H3n可區(qū)別數的一個上界，即，當n≥6時，H3n的可區(qū)別數不超過5. 2在給出了n維超立方體三次冪H3n可區(qū)別數的一個上界的基礎上，對維數不超過7的超立方體三次冪的可區(qū)別數進行了研究

3、.通過適當地選取頂點得到了H33的可區(qū)別數為8,H34的可區(qū)別數為5，H36和H37的可區(qū)別數都為2，及H35可區(qū)別數的一個上界為3. 3提出了圖的邊可區(qū)別數概念.給出了n階路Pn和n階圈Cn的邊可區(qū)別數；根據n維超立方體Hn及其p次冪Hpn的結構特性，對n維超立方體Hn，n維超立方體二次冪H2n和n維超立方體p(＞2)次冪Hpn的邊可區(qū)別數進行了研究，得到了n維超立方體及其二次冪H2n的邊可區(qū)別數，和n維超立方體高次冪Hpn的