An L(2, 1)-labeling of a graph 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 d(x, y) = 1 and |f(x)-f(y)| ≥ 1 ifd(x, y) = 2. The ...An L(2, 1)-labeling of a graph 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 d(x, y) = 1 and |f(x)-f(y)| ≥ 1 ifd(x, y) = 2. The L(2, 1)-labeling number λ(G) of G is the smallest number k such that G has an L(2, 1)-labeling with max{f(v) : v ∈ V(G)} = k. We study the L(3, 2, 1)-labeling which is a generalization of the L(2, 1)-labeling on the graph formed by the (Cartesian) product and composition of 3 graphs and derive the upper bounds of λ3(G) of the graph.展开更多
Let G be an outerplanar graph with maximum degree △. Let χ(G^2) and A(G) denote the chromatic number of the square and the L(2, 1)-labelling number of G, respectively. In this paper we prove the following resu...Let G be an outerplanar graph with maximum degree △. Let χ(G^2) and A(G) denote the chromatic number of the square and the L(2, 1)-labelling number of G, respectively. In this paper we prove the following results: (1) χ(G^2) = 7 if △= 6; (2) λ(G) ≤ △ +5 if △ ≥ 4, and ),(G)≤ 7 if △ = 3; and (3) there is an outerplanar graph G with △ = 4 such that )λ(G) = 7. These improve some known results on the distance two labelling of outerplanar graphs.展开更多
基金Supported by the Natural Science Foundation of Education Ministry of Anhui Province (No.KJ2010B138)the Foundation for the Excellent Young Talents of Anhui Province(No.2010SQRL136ZD)the Natural Science Foundation of Chuzhou University(No.2008kj013B)
文摘An L(2, 1)-labeling of a graph 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 d(x, y) = 1 and |f(x)-f(y)| ≥ 1 ifd(x, y) = 2. The L(2, 1)-labeling number λ(G) of G is the smallest number k such that G has an L(2, 1)-labeling with max{f(v) : v ∈ V(G)} = k. We study the L(3, 2, 1)-labeling which is a generalization of the L(2, 1)-labeling on the graph formed by the (Cartesian) product and composition of 3 graphs and derive the upper bounds of λ3(G) of the graph.
基金Supported by the National Natural Science Foundation of China(No.10771197)
文摘Let G be an outerplanar graph with maximum degree △. Let χ(G^2) and A(G) denote the chromatic number of the square and the L(2, 1)-labelling number of G, respectively. In this paper we prove the following results: (1) χ(G^2) = 7 if △= 6; (2) λ(G) ≤ △ +5 if △ ≥ 4, and ),(G)≤ 7 if △ = 3; and (3) there is an outerplanar graph G with △ = 4 such that )λ(G) = 7. These improve some known results on the distance two labelling of outerplanar graphs.