TY - JOUR

T1 - L(2, 1)-labelings of subdivisions of graphs

AU - Chang, Fei Huang

AU - Chia, Ma Lian

AU - Kuo, David

AU - Liaw, Sheng Chyang

AU - Tsai, Meng Hsuan

N1 - Publisher Copyright:
© 2014 Elsevier B.V. All rights reserved.

PY - 2015/2/6

Y1 - 2015/2/6

N2 - Given a graph G and a function h from E(G) to double-struck N, the h-subdivision of G, denoted by G(h), is the graph obtained from G by replacing each edge uv in G with a path P : uxuv1xuv2 . . . xuvn-1 v, where n = h(uv). When h(e) = c is a constant for all e ∈ E(G), we use G(c) to replace G(h). Given a graph G, an L(2, 1)-labeling of G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x) - f(y)| ≥ 2 if dG(x, y) = 1, and |f(x) - f(y)| ≥ 1 if dG(x, y) = 2. A k-L(2, 1)-labeling is an L(2, 1)-labeling such that no label is greater than k. The L(2, 1)-labeling number of G, denoted by λ(G), is the smallest number k such that G has a k-L(2, 1)-labeling. We study the L(2, 1)-labeling numbers of subdivisions of graphs in this paper. We prove that λ(G(3)) = Δ(G) + 1 for any graph G with Δ(G) ≥ 4, and show that λ(G(h)) = Δ(G) + 1 if Δ(G) ≥ 5 and h is a function from E(G) to double-struck N so that h(e) ≥ 3 for all e ∈ E(G), or if Δ(G) ≥ 4 and h is a function from E(G) to double-struck N so that h(e) ≥ 4 for all e ∈ E(G).

AB - Given a graph G and a function h from E(G) to double-struck N, the h-subdivision of G, denoted by G(h), is the graph obtained from G by replacing each edge uv in G with a path P : uxuv1xuv2 . . . xuvn-1 v, where n = h(uv). When h(e) = c is a constant for all e ∈ E(G), we use G(c) to replace G(h). Given a graph G, an L(2, 1)-labeling of G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x) - f(y)| ≥ 2 if dG(x, y) = 1, and |f(x) - f(y)| ≥ 1 if dG(x, y) = 2. A k-L(2, 1)-labeling is an L(2, 1)-labeling such that no label is greater than k. The L(2, 1)-labeling number of G, denoted by λ(G), is the smallest number k such that G has a k-L(2, 1)-labeling. We study the L(2, 1)-labeling numbers of subdivisions of graphs in this paper. We prove that λ(G(3)) = Δ(G) + 1 for any graph G with Δ(G) ≥ 4, and show that λ(G(h)) = Δ(G) + 1 if Δ(G) ≥ 5 and h is a function from E(G) to double-struck N so that h(e) ≥ 3 for all e ∈ E(G), or if Δ(G) ≥ 4 and h is a function from E(G) to double-struck N so that h(e) ≥ 4 for all e ∈ E(G).

KW - (2, 1)-total labeling

KW - L(2, 1)-labeling

KW - Subdivision

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

U2 - 10.1016/j.disc.2014.09.006

DO - 10.1016/j.disc.2014.09.006

M3 - 期刊論文

AN - SCOPUS:84908542053

SN - 0012-365X

VL - 338

SP - 248

EP - 255

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -