Publication details
Distance constrained labelings of planar graphs with no short cycles
| Authors | |
|---|---|
| Year of publication | 2009 |
| Type | Article in Periodical |
| Magazine / Source | Discrete Applied Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.dam.2008.08.013 |
| Keywords | L(p, q)-labeling; Distance constrained labeling; Planar graphs with no short cycles |
| Description | 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. |