Distance constrained labelings of planar graphs with no short cycles

DVORAK, Z; Daniel KRÁĽ; P NEJEDLY a R SKREKOVSKI. Distance constrained labelings of planar graphs with no short cycles. Discrete Applied Mathematics. AMSTERDAM: Elsevier B.V., 2009, roč. 157, č. 12, s. 2634-2645. ISSN 0166-218X. Dostupné z: https://dx.doi.org/10.1016/j.dam.2008.08.013.

Základní údaje

Originální název

Distance constrained labelings of planar graphs with no short cycles

Autoři

DVORAK, Z; Daniel KRÁĽ; P NEJEDLY a R SKREKOVSKI

Vydání

Discrete Applied Mathematics, AMSTERDAM, Elsevier B.V. 2009, 0166-218X

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.816

DOI

http://dx.doi.org/10.1016/j.dam.2008.08.013

UT WoS

000267627800007

Klíčová slova anglicky

L(p, q)-labeling; Distance constrained labeling; Planar graphs with no short cycles

---

Anotace

V originále

Motivated by a conjecture of Wang and Lih, we show that every planar graph of girth at least seven and maximum degree Delta >= 190 + 2[p/q] has an L(p, q)-labeling of span at most 2p + q Delta - 2. Since the optimal span of an L(p. 1)-labeling of an infinite Delta-regular tree is 2p + Delta - 2, the obtained bound is the best possible for any p >= 1 and q = 1. (C) 2008 Elsevier B.V. All rights reserved.