Distance three labelings of trees

Fiala, J.; Golovach, P.A.; Kratochvil, J.; Lidický, B.; Paulusma, D.

doi:10.1016/j.dam.2011.02.004

Distance three labelings of trees

Fiala, J.; Golovach, P.A.; Kratochvil, J.; Lidický, B.; Paulusma, D.

Authors

J. Fiala

P.A. Golovach

J. Kratochvil

B. Lidický

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Abstract

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 whether the minimum span attains the lower bound is an -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 on the labeling.

Citation

Fiala, J., Golovach, P., Kratochvil, J., Lidický, B., & Paulusma, D. (2012). Distance three labelings of trees. Discrete Applied Mathematics, 160(6), 764-779. https://doi.org/10.1016/j.dam.2011.02.004

Journal Article Type	Article
Publication Date	Apr 1, 2012
Deposit Date	Dec 6, 2011
Journal	Discrete Applied Mathematics
Print ISSN	0166-218X
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	160
Issue	6
Pages	764-779
DOI	https://doi.org/10.1016/j.dam.2011.02.004
Keywords	Distance constrained graph labeling, Linear distance, Circular distance.
Public URL	https://durham-repository.worktribe.com/output/1533574