Distance three labelings of trees

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125746" target="_blank" >RIV/00216208:11320/12:10125746 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.dam.2011.02.004" target="_blank" >http://dx.doi.org/10.1016/j.dam.2011.02.004</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.dam.2011.02.004" target="_blank" >10.1016/j.dam.2011.02.004</a>

Result language
angličtina
Original language name
Distance three labelings of trees
Original language description
An L(2, 1. 1)-labeling of a graph G assigns nonnegative integers to the vertices of G in such a way that labels of adjacent vertices differ by at least two, while vertices that are at distance at most three are assigned different labels. The maximum label used is called the span of the labeling, and the aim is to minimize this value. We show that the minimum span of an L(2, 1, 1)-labeling of a tree can be bounded by a lower and an upper bound with difference one. Moreover, we show that deciding whetherthe minimum span attains the lower bound is an NP-complete problem. This answers a known open problem, which was recently posed by King, Ras, and Zhou as well. We extend some of our results to general graphs and/or to more general distance constraints onthe labeling.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)