On The Distinguishing Number Of Hypercubes

This paper investigates mainly the structural properties of the hypercube---the distinguishing number of the cube of hypercube and the edge distinguishing number of hypercube and its p powers. The distinguishing number of a graph G is the minimum number of the distinguishing labelings (colors) of the vertices in G for which destroys the symmetries of G;The edge distinguishing number of a graph G is the minimum number of the distinguishing labelings (colors) of the edges in G for which destroys the symmetries of G.For the distinguishing number of a graph G, Bogstad and Cowen investigated the distinguishing number of the hypercube and its square, and proposed a conjecture in Discrete Math. 2004 as follows: for fixed p, when n is sufficiently large, the distinguishing number of the p powers of the n-dimensional hypercube equals to 2. Based on the conjecture, this paper studies as follow.1 Based on the structural properties of the p powers of the n-dimensional hypercube, this paper studies the relations between the distance and hamming distance between its vertices, presents the sufficient and necessary conditions for determining the vertex coordinate, and combines with the methods of the "spine" technology and vertices coloring, and then studies the distinguishing number of the cube of the n(=6)-dimensional hypercube, gets the upper boundary of the distinguishing number of H_n³ is 5 for n ≥ 6.2 On the basis of getting an upper boundary of the distinguishing number of the cube of the n(=6)-dimensional hypercube H_n³, this paper studies the distinguishing number of the cube of the n(≤7)-dimensional hypercube, obtains the distinguishing number of graph H₃³, H₄³, H₆³ and H₇³ is 5, 8, 2 and 2, respectively, and the upper boundary of the distinguishing number of graph H₅³ is 3 by selecting vertices properly.3 Based on the distinguishing number of graph, this paper proposes the edge distinguishing number of graph, and offers the edge distinguishing number of then - vertex cycle Cn and the n - vertex path Pn. According to the structural properties of the n - dimensional hypercube graph Hn and its p powers HI, this paper studies the edge distinguishing number of the n - dimensional hypercube graph Hn, the square of the n - dimensional hypercube graph Hi and the /?(> 2) powers of the n -dimensional hypercube graph H*, and obtains the edge distinguishing number of the n - dimensional hypercube graph and its square â–  and an upper boundary of the p(> 2) powers of the n - dimensional hypercube graph, namely, the edge distinguishing number of graph #2 is 3 for n - 2 , and 2 for n ï¿¡ 3 , the edge distinguishing number of graph Hi is 2 for n a 6 , and the upper boundary of the edge distinguishing number of graph Hpn is 3 for n * 4 and n * p > 2.