On distinguishing and distinguishing chromatic numbers of hypercubes
Werner Klöckl
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 419-429 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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ℵ₀)=2 and χD(Qℵ₀)=3, where Qℵ₀ denotes the hypercube of countable dimension. We also show that χD(Q₄)=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.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270608 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1416,
     author = {Werner Kl\"ockl},
     title = {On distinguishing and distinguishing chromatic numbers of hypercubes},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {419-429},
     zbl = {1173.05020},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1416}
}

Werner Klöckl. On distinguishing and distinguishing chromatic numbers of hypercubes. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 419-429. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1416/

[000] [1] M.O. Albertson, Distinguishing Cartesian powers of graphs, Electron. J. Combin. 12 (2005) N17. | Zbl 1082.05047

[001] [2] M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996) R18. | Zbl 0851.05088

[002] [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. | Zbl 1044.05039

[003] [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. | Zbl 1154.05029

[004] [5] J.O. Choi, S.G. Hartke and H. Kaul, Distinguishing chromatic number of Cartesian products of graphs, submitted. | Zbl 1216.05030

[005] [6] K.T. Collins and A.N. Trenk, The distinguishing chromatic number, Electr. J. Combin. 13 (2006) R16. | Zbl 1081.05033

[006] [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. | Zbl 1205.05198

[007] [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.

[008] [9] W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006) 250-260, doi: 10.1002/jgt.20190. | Zbl 1108.05080