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

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

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

3、.通過(guò)適當(dāng)?shù)剡x取頂點(diǎn)得到了H33的可區(qū)別數(shù)為8,H34的可區(qū)別數(shù)為5，H36和H37的可區(qū)別數(shù)都為2，及H35可區(qū)別數(shù)的一個(gè)上界為3. 3提出了圖的邊可區(qū)別數(shù)概念.給出了n階路Pn和n階圈Cn的邊可區(qū)別數(shù)；根據(jù)n維超立方體Hn及其p次冪Hpn的結(jié)構(gòu)特性，對(duì)n維超立方體Hn，n維超立方體二次冪H2n和n維超立方體p(＞2)次冪Hpn的邊可區(qū)別數(shù)進(jìn)行了研究，得到了n維超立方體及其二次冪H2n的邊可區(qū)別數(shù)，和n維超立方體高次冪Hpn的