On the local distinguishing numbers of cycles

Consider the induced subgraph of a labeled graph G rooted at vertex v, denoted by N-v(i), where V(N-v(i)) = {u: 0 less than or equal to d(u, v) less than or equal to i}. A labeling of the vertices of G, Phi, : V(G) --> {1,..., r} is said to be i-local distinguishing if For All u, v is an element of V(G),u not equal v, N-v(i) is not isomorphic to N-u(i) under Phi. The ith local distinguishing number of G, LDi(G) is the minimum r such that G has an i-local distinguishing labeling that uses r colors. LDi(G) is a generalization of the distinguishing number D(G) as defined in Albertson and Collins (1996). An exact value for LD1(C-n) is computed for each n. It is shown that LDi(C-n)=Omega(n(1/(2i+1))). In addition, LDi(C-n) less than or equal to 24(2i + 1)n(1/(2i+1))(log n)(2i/(2i+1)) for constant i was proven using probabilistic methods. Finally, it is noted that for almost all graphs G, LD1(G) = O(log n). (C) 1999 Elsevier Science B.V. All rights reserved.