tailieunhanh - Báo cáo toán học: "Distinguishing Cartesian Powers of Graph"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Distinguishing Cartesian Powers of Graphs. | Distinguishing Cartesian Powers of Graphs Michael O. Albertson Department of Mathematics Smith College Northampton MA 01063 USA albertson@ Submitted Feb 26 2005 Accepted Sep 1 2005 Published Sep 19 2005 Mathematics Subject Classifications 05C25 05C78 Abstract Given a graph G a labeling c V G 1 2 . d is said to be d-distinguishing if the only element in Aut G that preserves the labels is the identity. The distinguishing number of G denoted by D G is the minimum d such that G has a d-distinguishing labeling. If GũH denotes the Cartesian product of G and H let G GBG and G GOGr . A graph G is said to be prime with respect to the Cartesian product if whenever G G1nG2 then either G1 or G2 is a singleton vertex. This paper proves that if G is a connected prime graph then D Gr 2 whenever r 4. 1 Introduction Given a graph G a labeling c V G 1 2 . d is d-distinguishing if the only element in Aut G that preserves the labels is the identity. The idea is that the labeling together with the structure of G uniquely identifies every vertex. Formally c is said to be d-distinguishing if b 2 Aut G and c b x c x for all x 2 V G implies that b id. The distinguishing number of G denoted by D G is the minimum d such that G has a d-distinguishing labeling. It is a measure of the relative symmetry of G. It is immediate that D Kn n and when q p D Kpq q. It is straightforward to see that D Kn n n 1. The original paper on distinguishing 1 was inspired by a recreational puzzle 5 . The solution requires showing that if n 6 then D Cn 2. The attraction of this puzzle is the contrast with smaller cycles where D Cn 3 when 3 n 5. The inspiration for this paper is the solution to the problem of distinguishing the generalized cubes. Let Qr denote the r-dimensional hypercube V Qr x x1 . xr xi 2 Z2 and xy 2 E Qr if x and y differ in exactly one coordinate. Note that Q2 C4 Q3 is the standard cube and D Q2 D Q3 3. THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 N17 1 The Cartesian or box .