Cheng, C. T.; Cowen, L. J. On the local distinguishing numbers of cycles. (English) Zbl 0932.05042 Discrete Math. 196, No. 1-3, 97-108 (1999). From the authors’ abstract: Consider the induced subgraph of a labeled graph \(G\) rooted at vertex \(v\), denoted by \(N^i_v\), where \(V(N^i_v) = \{u:0 \leq d(u,v) \leq i\}\). A labeling of the vertices of \(G\), \(\phi:V(G) \rightarrow \{1, \dots, r\}\) is said to be \(i\)-local distinguishing if for all distinct \(u, v \in V(G)\), \(N^i_v\) is not isomorphic to \(N^i_u\) under \(\phi\). The \(i\)th local distinguishing number of \(G, ~ LD^i(G)\) is the minimum \(r\) such that \(G\) has an \(i\)-local distinguishing labeling that uses \(r\) colors. \(LD^i(G)\) is a generalization of the distinguishing number \(D(G)\) as defined in M. O. Albertson and K. L. Collins [Electron. J. Comb. 3, No. 1, Research paper R18 (1996); printed version J. Comb. 3, No. 1, 259-275 (1996; Zbl 0851.05088)]. An exact value for \(LD^1(C_n)\) is computed for each \(n\). It is shown that \(LD^i(C_n) = \Omega (n^{1/(2i+1)}\)). In addition, \(LD^i (C_n) \leq 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\), \(LD^1(G) = O(\log n)\). Reviewer: E.M.Palmer (East Lansing) Cited in 2 ReviewsCited in 4 Documents MSC: 05C30 Enumeration in graph theory 05C38 Paths and cycles Keywords:labeled graph; distinguishing labeling; distinguishing number Citations:Zbl 0851.05088 PDFBibTeX XMLCite \textit{C. T. Cheng} and \textit{L. J. Cowen}, Discrete Math. 196, No. 1--3, 97--108 (1999; Zbl 0932.05042) Full Text: DOI References: [1] Albertson, M.; Collins, K., Symmetry breaking in graphs, Electron. J. Combin., 3 (1996) · Zbl 0851.05088 [2] N. Alon, personal communication.; N. Alon, personal communication. [3] Babai, L.; Erdős, P.; Selkow, S., Random graph isomorphism, SIAM J. Comput., 3, 628-635 (1980) · Zbl 0454.05038 [4] Bollobás, B., Degree sequences of random graphs, Trans. Amer. Math. Soc., 267, 41-52 (1981) · Zbl 0479.05038 [5] Lempel, A., m-ary closed sequences, J. Comb. Theory Ser. A, 10, 253-258 (1971) · Zbl 0224.05008 [6] Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0849.68039 [7] West, D., Introduction to Graph Theory (1996), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0845.05001 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.