On distinguishing and distinguishing chromatic numbers of hypercubes

Werner Klöckl

Discussiones Mathematicae Graph Theory (2008)

  • Volume: 28, Issue: 3, page 419-429
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Werner Klöckl. "On distinguishing and distinguishing chromatic numbers of hypercubes." Discussiones Mathematicae Graph Theory 28.3 (2008): 419-429. <http://eudml.org/doc/270608>.

@article{WernerKlöckl2008,
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_ℵ₀) = 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.},
author = {Werner Klöckl},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distinguishing number; distinguishing chromatic number; hypercube; weak Cartesian product},
language = {eng},
number = {3},
pages = {419-429},
title = {On distinguishing and distinguishing chromatic numbers of hypercubes},
url = {http://eudml.org/doc/270608},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Werner Klöckl
TI - On distinguishing and distinguishing chromatic numbers of hypercubes
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 3
SP - 419
EP - 429
AB - 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.
LA - eng
KW - distinguishing number; distinguishing chromatic number; hypercube; weak Cartesian product
UR - http://eudml.org/doc/270608
ER -

References

top
  1. [1] M.O. Albertson, Distinguishing Cartesian powers of graphs, Electron. J. Combin. 12 (2005) N17. Zbl1082.05047
  2. [2] M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996) R18. Zbl0851.05088
  3. [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. Zbl1044.05039
  4. [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. Zbl1154.05029
  5. [5] J.O. Choi, S.G. Hartke and H. Kaul, Distinguishing chromatic number of Cartesian products of graphs, submitted. Zbl1216.05030
  6. [6] K.T. Collins and A.N. Trenk, The distinguishing chromatic number, Electr. J. Combin. 13 (2006) R16. Zbl1081.05033
  7. [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. Zbl1205.05198
  8. [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. [9] W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006) 250-260, doi: 10.1002/jgt.20190. Zbl1108.05080

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.