| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4654885 | European Journal of Combinatorics | 2007 | 8 Pages |
Abstract
The distinguishing number D(G)D(G) of a graph GG is the least integer dd such that there is a dd-labeling of the vertices of GG which is not preserved by any nontrivial automorphism. For a graph GG let GrGr be the rrth power of GG with respect to the Cartesian product. It is proved that D(Gr)=2D(Gr)=2 for any connected graph GG with at least 3 vertices and for any r≥3r≥3. This confirms and strengthens a conjecture of Albertson. Other graph products are also considered and a refinement of the Russell and Sundaram motion lemma is proved.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Sandi Klavžar, Xuding Zhu,