A note on adjacent vertex distinguishing colorings of graphs

• DOI: 10.1016/j.dam.2015.12.005
• Publication Date: 2016-01-02T13:01:47Z
• Authors: M. Axenovich; J. Harant; J. Przybyło; R. Soták; M. Voigt; J. Weidelich
• Keywords: Neighbourhood (mathematics)

Abstract For an assignment of numbers to the vertices of a graph, let S [ u ] be the sum of the labels of all the vertices in the closed neighborhood of u , for a vertex u . Such an assignment is called closed distinguishing if S [ u ] ≠ S [ v ] for any two adjacent vertices u and v unless the closed neighborhoods of u and v coincide. In this note we investigate dis [ G ] , the smallest integer k such that there is a closed distinguishing labeling of G using labels from { 1 , … , k } . We prove that dis [ G ] ≤ Δ 2 − Δ + 1 , where Δ is the maximum degree of G . This result is sharp. We also consider a list-version of the function dis [ G ] and give a number of related results.