Back to Search
Start Over
The distinguishing number of Cartesian products of complete graphs
- Source :
-
European Journal of Combinatorics . May2008, Vol. 29 Issue 4, p922-929. 8p. - Publication Year :
- 2008
-
Abstract
- Abstract: The distinguishing number of a graph is the least integer such that has a labeling with labels that is preserved only by a trivial automorphism. We prove that Cartesian products of relatively prime graphs whose sizes do not differ too much can be distinguished with a small number of colors. We determine the distinguishing number of the Cartesian product for all and , either explicitly or by a short recursion. We also introduce column-invariant sets of vectors and prove a switching lemma that plays a key role in the proofs. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 01956698
- Volume :
- 29
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- European Journal of Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 31674982
- Full Text :
- https://doi.org/10.1016/j.ejc.2007.11.018