Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Distance three labelings of trees.

Fiala, J. and Golovach, P.A. and Kratochvil, J. and Lidicky, B. and Paulusma, Daniel (2012) 'Distance three labelings of trees.', Discrete applied mathematics. .

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.

Item Type:Article
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1016/j.dam.2011.02.004
Record Created:07 Dec 2011 14:35
Last Modified:03 Apr 2013 16:22

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library