Szczegóły publikacji
Opis bibliograficzny
A note on adjacent vertex distinguishing colorings of graphs / M. Axenovich, J. Harant, J. PRZYBYŁO, R. Soták, M. Voigt, J. Weidelich // Discrete Applied Mathematics ; ISSN 0166-218X. — 2016 — vol. 205, s. 1–7. — Bibliogr. s. 6–7, Abstr. — Publikacja dostępna online od: 2016-01-02
Autorzy (6)
- Axenovich Maria A.
- Harant Jochen
- AGHPrzybyło Jakub
- Soták Roman
- Voigt Margit
- Weidelich J.
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 102517 |
|---|---|
| Data dodania do BaDAP | 2016-12-16 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.dam.2015.12.005 |
| Rok publikacji | 2016 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Applied 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] not equal 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] <= 42 Delta(2) - Delta + 1, where Delta 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. (C) 2015 Elsevier B.V. All rights reserved.