Distance three labelings of trees

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Distance three labelings of trees

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Distance three labelings of trees

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2012

Kód důvěrnosti údajů

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

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

160

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

16

Strana od-do

764-779

Kód UT WoS článku

000302981900008

EID výsledku v databázi Scopus

—