Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.dam.2015.12.005 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Vertex-distinguishing,Labeling,Coloring,List-vertex-distinguishing | Integer,Discrete mathematics,Graph,Combinatorics,Bound graph,Vertex (geometry),Neighbourhood (graph theory),Degree (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
205 | C | 0166-218X |
Citations | PageRank | References |
4 | 0.41 | 8 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Axenovich | 1 | 209 | 33.90 |
| Jochen Harant | 2 | 217 | 30.62 |
| Jakub Przybyło | 3 | 210 | 27.55 |
| Roman Soták | 4 | 128 | 24.06 |
| Margit Voigt | 5 | 4 | 0.41 |
| Jenny Weidelich | 6 | 4 | 0.41 |