TY - JOUR

T1 - A tight upper bound on the (2, 1)-total labeling number of outerplanar graphs

AU - Hasunuma, Toru

AU - Ishii, Toshimasa

AU - Ono, Hirotaka

AU - Uno, Yushi

N1 - Funding Information:
This research is partly supported by Inamori Foundation and Grant-in-Aid for Scientific Research (KAKENHI), Nos. 19500016 , 20700002 , 21500017 , 21680001 , and 22650004 .

PY - 2012/7

Y1 - 2012/7

N2 - A (2,1)-total labeling of a graph G is an assignment f from the vertex set V(G) and the edge set E(G) to the set {0,1,...,k} of nonnegative integers such that |f(x)-f(y)|≥2 if x is a vertex and y is an edge incident to x, and |f(x)-f(y)|≥1 if x and y are a pair of adjacent vertices or a pair of adjacent edges, for all x and y in V(G) ∪ E(G). The (2,1)-total labeling number λ T 2 (G) of G is defined as the minimum k among all possible (2,1)-total labelings of G. In 2007, Chen and Wang conjectured that all outerplanar graphs G satisfy λ T 2 (G)≤Δ(G)+2, where Δ(G) is the maximum degree of G. They also showed that it is true for G with Δ(G)≥5. In this paper, we solve their conjecture, by proving that λ T 2 (G)≤Δ(G)+2, even when Δ(G)≤4.

AB - A (2,1)-total labeling of a graph G is an assignment f from the vertex set V(G) and the edge set E(G) to the set {0,1,...,k} of nonnegative integers such that |f(x)-f(y)|≥2 if x is a vertex and y is an edge incident to x, and |f(x)-f(y)|≥1 if x and y are a pair of adjacent vertices or a pair of adjacent edges, for all x and y in V(G) ∪ E(G). The (2,1)-total labeling number λ T 2 (G) of G is defined as the minimum k among all possible (2,1)-total labelings of G. In 2007, Chen and Wang conjectured that all outerplanar graphs G satisfy λ T 2 (G)≤Δ(G)+2, where Δ(G) is the maximum degree of G. They also showed that it is true for G with Δ(G)≥5. In this paper, we solve their conjecture, by proving that λ T 2 (G)≤Δ(G)+2, even when Δ(G)≤4.

UR - http://www.scopus.com/inward/record.url?scp=84860841442&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860841442&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2011.12.020

DO - 10.1016/j.jda.2011.12.020

M3 - Article

AN - SCOPUS:84860841442

SN - 1570-8667

VL - 14

SP - 189

EP - 206

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

ER -