The distinguishing number of the direct product and wreath product action
Melody Chan
University of Cambridge Cambridge England Cambridge England
DOI: 10.1007/s10801-006-0006-7
Abstract
Let G be a group acting faithfully on a set X. The distinguishing number of the action of G on X, denoted D G( X), is the smallest number of colors such that there exists a coloring of X where no nontrivial group element induces a color-preserving permutation of X. In this paper, we consider the distinguishing number of two important product actions, the wreath product and the direct product. Given groups G and H acting on sets X and Y respectively, we characterize the distinguishing number of the wreath product G \? Y H in terms of the number of distinguishing colorings of X with respect to G and the distinguishing number of the action of H on Y. We also prove a recursive formula for the distinguishing number of the action of the Cartesian product of two symmetric groups S m \times S n on [ m] \times [ n].
Pages: 331–345
Keywords: keywords symmetry group; symmetry breaking; distinguishing number; wreath product; direct product
Full Text: PDF
References
1. M. Albertson and K. Collins, “An introduction to symmetry breaking in graphs,” Graph Theory Notes N.Y. 30 (1996), 6-7.
2. M. Albertson and K. Collins, “Symmetry breaking in graphs,” Electronic J. Combin. 3 (1996).
3. B. Bogstad and L. Cowen, “The distinguishing number of the hypercube,” Discrete Math. 283 (2004), 29-35.
4. P.J. Cameron, Permutation Groups, in Handbook of Combinatorics, R.L. Graham, M. Gr\ddot otschel, L. Lovász (eds.), Cambridge, 1995, vol. 1, pp. 611-645.
5. M. Chan, “The distinguishing number of the augmented cube and hypercube powers,” preprint, available at http://arxiv.org/pdf/math.CO/0601361 .
6. M. Chan, “The maximum distinguishing number of a group,” to appear in Electronic J. Combinatorics, available at http://arxiv.org/pdf/math.CO/0601359.
7. C.C.T. Cheng, “Three problems in graph labeling,” Ph.D. Thesis, Department of Mathematical Sciences, Johns Hopkins University, 1999.
8. E. Dobson and J. Morris, “Automorphism groups of wreath product digraphs,” submitted.
9. M. Hall, The Theory of Groups, Macmillan, New York, 1959.
10. R.L. Hemminger, “The lexicographic product of graphs,” Duke Math. J. 33 (1966), 499-501.
11. K. Potanka, “Groups, graphs and symmetry breaking,” Masters Thesis, Department of Mathematics, Virginia Polytechnic Institute, 1998.
12. G. Sabidussi, “The composition of graphs,” Duke Math. J. 26 (1959), 693-696.
13. J. Tymoczko, “Distinguishing numbers for graphs and groups,” Electronic J. Combin. 11(1) (2004).
2. M. Albertson and K. Collins, “Symmetry breaking in graphs,” Electronic J. Combin. 3 (1996).
3. B. Bogstad and L. Cowen, “The distinguishing number of the hypercube,” Discrete Math. 283 (2004), 29-35.
4. P.J. Cameron, Permutation Groups, in Handbook of Combinatorics, R.L. Graham, M. Gr\ddot otschel, L. Lovász (eds.), Cambridge, 1995, vol. 1, pp. 611-645.
5. M. Chan, “The distinguishing number of the augmented cube and hypercube powers,” preprint, available at http://arxiv.org/pdf/math.CO/0601361 .
6. M. Chan, “The maximum distinguishing number of a group,” to appear in Electronic J. Combinatorics, available at http://arxiv.org/pdf/math.CO/0601359.
7. C.C.T. Cheng, “Three problems in graph labeling,” Ph.D. Thesis, Department of Mathematical Sciences, Johns Hopkins University, 1999.
8. E. Dobson and J. Morris, “Automorphism groups of wreath product digraphs,” submitted.
9. M. Hall, The Theory of Groups, Macmillan, New York, 1959.
10. R.L. Hemminger, “The lexicographic product of graphs,” Duke Math. J. 33 (1966), 499-501.
11. K. Potanka, “Groups, graphs and symmetry breaking,” Masters Thesis, Department of Mathematics, Virginia Polytechnic Institute, 1998.
12. G. Sabidussi, “The composition of graphs,” Duke Math. J. 26 (1959), 693-696.
13. J. Tymoczko, “Distinguishing numbers for graphs and groups,” Electronic J. Combin. 11(1) (2004).