Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419228 | Discrete Applied Mathematics | 2016 | 7 Pages |
Abstract
For an assignment of numbers to the vertices of a graph, let S[u]S[u] be the sum of the labels of all the vertices in the closed neighborhood of uu, for a vertex uu. Such an assignment is called closed distinguishing if S[u]≠S[v]S[u]≠S[v] for any two adjacent vertices uu and vv unless the closed neighborhoods of uu and vv coincide. In this note we investigate dis[G], the smallest integer kk such that there is a closed distinguishing labeling of GG using labels from {1,…,k}{1,…,k}. We prove that dis[G]≤Δ2−Δ+1, where ΔΔ is the maximum degree of GG. This result is sharp. We also consider a list-version of the function dis[G] and give a number of related results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
M. Axenovich, J. Harant, J. Przybyło, R. Soták, M. Voigt, J. Weidelich,