On the local distinguishing numbers of cycles

✍ Scribed by C.T Cheng; L.J Cowen

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 836 KB
• Volume: 196
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(98)00167-8

✦ Synopsis

Consider the induced subgraph of a labeled graph G rooted at vertex o, denoted by N,!, where V(N,f)= {u: O<d(u,u)<i}.

A labeling of the vertices of G, @ : V(G)-+ {l,...,r} is said to be ' i-local distinguishing if Vu, II E V(G), u # u, N, is not isomorphic to NL under @. The ith local distinguishing number of G, LD'(G) is the minimum r such that G has an i-local distinguishing labeling that uses Y colors. LD'(G) is a generalization of the distinguishing number D(G) as defined in Albertson and Collins (1996).

An exact value for LD'(C,,) is computed for each n. It is shown that LD'(C,,) = O(n'1(2i+')). In addition, LD'(C,,) <24(2i + 1 )n"(*'+')(log n)2i'(2'+') for constant i was proven using probabilistic methods. Finally, it is noted that for almost all graphs G, LD'(G) = O(logn).