Distance constrained labelings of planar graphs with no short cycles

DVORAK, Z; Daniel KRÁĽ; P NEJEDLY and R SKREKOVSKI. Distance constrained labelings of planar graphs with no short cycles. Discrete Applied Mathematics. AMSTERDAM: Elsevier B.V., 2009, vol. 157, No 12, p. 2634-2645. ISSN 0166-218X. Available from: https://dx.doi.org/10.1016/j.dam.2008.08.013.

Basic information

Original name

Distance constrained labelings of planar graphs with no short cycles

Authors

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

Edition

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

---

Other information

Language

English

Type of outcome

Article in a journal

Confidentiality degree

is not subject to a state or trade secret

Impact factor

Impact factor: 0.816

DOI

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

UT WoS

000267627800007

Keywords in English

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

---

Abstract

In the original language

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.