# Characterization Results for theL(2, 1, 1)-Labeling Problem on Trees

Discussiones Mathematicae Graph Theory (2017)

- Volume: 37, Issue: 3, page 611-622
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topXiaoling Zhang, and Kecai Deng. "Characterization Results for theL(2, 1, 1)-Labeling Problem on Trees." Discussiones Mathematicae Graph Theory 37.3 (2017): 611-622. <http://eudml.org/doc/288292>.

@article{XiaolingZhang2017,

abstract = {An L(2, 1, 1)-labeling of a graph G is an assignment of non-negative integers (labels) to the vertices of G such that adjacent vertices receive labels with difference at least 2, and vertices at distance 2 or 3 receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used, and the minimum span over all L(2, 1, 1)-labelings of G is called the L(2, 1, 1)-labeling number of G, denoted by λ2,1,1(G). It was shown by King, Ras and Zhou in [The L(h, 1, 1)-labelling problem for trees, European J. Combin. 31 (2010) 1295–1306] that every tree T has Δ2(T) − 1 ≤ λ2,1,1(T) ≤ Δ2(T), where Δ2(T) = maxuv∈E(T)(d(u) + d(v)). And they conjectured that almost all trees have the L(2, 1, 1)-labeling number attain the lower bound. This paper provides some sufficient conditions for λ2,1,1(T) = Δ2(T). Furthermore, we show that the sufficient conditions we provide are also necessary for trees with diameter at most 6.},

author = {Xiaoling Zhang, Kecai Deng},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {L(2, 1, 1)-labeling; tree; diameter},

language = {eng},

number = {3},

pages = {611-622},

title = {Characterization Results for theL(2, 1, 1)-Labeling Problem on Trees},

url = {http://eudml.org/doc/288292},

volume = {37},

year = {2017},

}

TY - JOUR

AU - Xiaoling Zhang

AU - Kecai Deng

TI - Characterization Results for theL(2, 1, 1)-Labeling Problem on Trees

JO - Discussiones Mathematicae Graph Theory

PY - 2017

VL - 37

IS - 3

SP - 611

EP - 622

AB - An L(2, 1, 1)-labeling of a graph G is an assignment of non-negative integers (labels) to the vertices of G such that adjacent vertices receive labels with difference at least 2, and vertices at distance 2 or 3 receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used, and the minimum span over all L(2, 1, 1)-labelings of G is called the L(2, 1, 1)-labeling number of G, denoted by λ2,1,1(G). It was shown by King, Ras and Zhou in [The L(h, 1, 1)-labelling problem for trees, European J. Combin. 31 (2010) 1295–1306] that every tree T has Δ2(T) − 1 ≤ λ2,1,1(T) ≤ Δ2(T), where Δ2(T) = maxuv∈E(T)(d(u) + d(v)). And they conjectured that almost all trees have the L(2, 1, 1)-labeling number attain the lower bound. This paper provides some sufficient conditions for λ2,1,1(T) = Δ2(T). Furthermore, we show that the sufficient conditions we provide are also necessary for trees with diameter at most 6.

LA - eng

KW - L(2, 1, 1)-labeling; tree; diameter

UR - http://eudml.org/doc/288292

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.