Informace o publikaci
Distance constrained labelings of planar graphs with no short cycles
| Autoři | |
|---|---|
| Rok publikování | 2009 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Discrete Applied Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.dam.2008.08.013 |
| Klíčová slova | L(p, q)-labeling; Distance constrained labeling; Planar graphs with no short cycles |
| Popis | 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. |