×

On the local distinguishing numbers of cycles. (English) Zbl 0932.05042

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)\).

MSC:

05C30 Enumeration in graph theory
05C38 Paths and cycles

Citations:

Zbl 0851.05088
PDFBibTeX XMLCite
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.