On distinquishing numbers
Werner Klöckl · Discussiones Mathematicae Graph Theory · 2008
The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism. The restriction to proper labelings leads to the denition of the distinguishing chromatic number D(G) of G. Extending these concepts to innite graphs we prove that D(Q@0 ) = 2 and D(Q@0 ) = 3, where Q@0 denotes the hypercube of countable dimension. We also show that D(Q4) = 4, thereby completing the investigation of nite hypercubes with respect to D. Our results extend work on nite graphs by Bogstad and Cowen on the distinguishing number and Choi, Hartke and Kaul on the distinguishing chromatic number.