Discussiones Mathematicae Graph Theory 28(3) (2008)
419-429
DOI: https://doi.org/10.7151/dmgt.1416
ON DISTINGUISHING AND DISTINGUISHING CHROMATIC NUMBERS OF HYPERCUBES
Werner Klöckl
Chair of Applied Mathematics
Montanuniversität Leoben, 8700 Leoben, Austria
e-mail: werner.kloeckl@mu-leoben.at
Abstract
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 definition of the distinguishing chromatic number χD(G) of G.Extending these concepts to infinite 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 finite hypercubes with respect to χD.
Our results extend work on finite graphs by Bogstad and Cowen on the distinguishing number and Choi, Hartke and Kaul on the distinguishing chromatic number.
Keywords: distinguishing number, distinguishing chromatic number, hypercube, weak Cartesian product.
2000 Mathematics Subject Classification: Primary: 05C25, 05C15; Secondary: 05C12.
References
| [1] | M.O. Albertson, Distinguishing Cartesian powers of graphs, Electron. J. Combin. 12 (2005) N17. |
| [2] | M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996) R18. |
| [3] | B. Bogstad and L.J. Cowen, The distinguishing number of hypercubes, Discrete Math. 283 (2004) 29-35, doi: 10.1016/j.disc.2003.11.018. |
| [4] | M. Chan, The distinguishing number of the augmented cube and hypercube powers, Discrete Math. 308 (2008) 2330-2336, doi: 10.1016/j.disc.2006.09.056. |
| [5] | J.O. Choi, S.G. Hartke and H. Kaul, Distinguishing chromatic number of Cartesian products of graphs, submitted. |
| [6] | K.T. Collins and A.N. Trenk, The distinguishing chromatic number, Electr. J. Combin. 13 (2006) R16. |
| [7] | W. Imrich, J. Jerebic and S. Klavžar, The distinguishing number of Cartesian products of complete graphs, Eur. J. Combin. 29 (2008) 922-927, doi: 10.1016/j.ejc.2007.11.018. |
| [8] | W. Imrich and S. Klavžar, Product Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization (Wiley-Interscience, New York, 2000). Structure and recognition, With a foreword by Peter Winkler. |
| [9] | W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006) 250-260, doi: 10.1002/jgt.20190. |
Received 18 October 2006
Revised 6 June 2008
Accepted 6 June 2008
Close