A tight upper bound on the (2, 1)-total labeling number of outerplanar graphs
A tight upper bound on the (2, 1)-total labeling number of outerplanar graphs
复制标题
DOI：
10.1016/j.jda.2011.12.020
复制
发表时间：
2009-11
期刊：
影响因子：
--
通讯作者：
Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno
中科院分区：
文献类型：
--
作者：
Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno
图G的(2，1)-全标号是指从顶点集V(G)和边集E(G)到集合{0，1，…，k}的非负整数，如果x是顶点，y是与x关联的边，则|f(X)−f(Y)|⩾2；如果x和y是一对相邻顶点或一对相邻边，则|f(X)−f(Y)|⩾1，对V(G)∪E(G)中的所有x和y。G的(2，1)-全标号λ2T(G)被定义为G的所有可能的(2，1)-全标号中的最小k。2007年，陈和王猜想所有外平面图都满足λ2T(G)⩽Δ(G)+2，其中Δ(G)是G的最大度。他们还证明了当G有Δ(G)⩾5时，G也是如此。本文证明了λ2T(G)⩽Δ(G)+2，即使当Δ(G)⩽4时也成立。
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 λ2T(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 λ2T(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 λ2T(G)⩽Δ(G)+2, even when Δ(G)⩽4.