A new sufficient condition for a tree T to have the (2,1)-total number

被引:0
作者
Shu, Qiaojun [1 ]
Wang, Weifan [2 ]
Wang, Yiqiao [3 ]
机构
[1] Hangzhou Dianzhi Univ, Sch Sci, Hangzhou 310018, Zhejiang, Peoples R China
[2] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China
[3] Beijing Univ Chinese Med, Sch Management, Beijing 100029, Peoples R China
关键词
(2,1)-total labelling; (2,1)-total number; Tree; Maximum degree; OUTERPLANAR GRAPHS; MAXIMUM DEGREE; (P; (D;
D O I
10.1007/s10878-016-0021-0
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
A k-(2, 1)-total labelling of a graph G is a mapping such that adjacent vertices or adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least 2. The (2, 1)-total number, denoted , is the minimum k such that G has a k-(2, 1)-total labelling. Let T be a tree with maximum degree . A vertex is called major if , minor if , and saturated if v is major and is adjacent to exactly major vertices. It is known that . In this paper, we prove that if every major vertex is adjacent to at most major vertices, and every minor vertex is adjacent to at most three saturated vertices, then . The result is best possible with respect to these required conditions.
引用
收藏
页码:1011 / 1020
页数:10
相关论文
共 19 条
[1]   The L(2,1)-labeling problem on graphs [J].
Chang, GJ ;
Kuo, D .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (02) :309-316
[2]   (2,1)-total labelling of outerplanar graphs [J].
Chen, Dong ;
Wang, Weifan .
DISCRETE APPLIED MATHEMATICS, 2007, 155 (18) :2585-2593
[3]   (2,1)-total labeling of trees with large maximum degree [J].
Chen, Dong ;
Shiu, Wai Chee ;
Shu, Qiaojun ;
Sun, Pak Kiu ;
Wang, Weifan .
DISCRETE APPLIED MATHEMATICS, 2015, 187 :61-69
[4]   LABELING GRAPHS WITH A CONDITION AT DISTANCE-2 [J].
GRIGGS, JR ;
YEH, RK .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (04) :586-595
[5]   A tight upper bound on the (2, 1)-total labeling number of outerplanar graphs [J].
Hasunuma, Toru ;
Ishii, Toshimasa ;
Ono, Hirotaka ;
Uno, Yushi .
JOURNAL OF DISCRETE ALGORITHMS, 2012, 14 :189-206
[6]   The (p, q)-total labeling problem for trees [J].
Hasunuma, Toru ;
Ishii, Toshimasa ;
Ono, Hirotaka ;
Uno, Yushi .
DISCRETE MATHEMATICS, 2012, 312 (08) :1407-1420
[7]   (p, 1)-Total labelling of graphs [J].
Havet, Frederic ;
Yu, Min-Li .
DISCRETE MATHEMATICS, 2008, 308 (04) :496-513
[8]   L(2,1)-labeling of hamiltonian graphs with maximum degree 3 [J].
Kang, Jeong-Hyun .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (01) :213-230
[9]   [r, s, t]-Colorings of graphs [J].
Kemnitz, Arnfried ;
Marangio, Massimiliano .
DISCRETE MATHEMATICS, 2007, 307 (02) :199-207
[10]   On (d, 1)-total numbers of graphs [J].
Lih, Ko-Wei ;
Liu, Daphne Der-Fen ;
Wang, Weifan .
DISCRETE MATHEMATICS, 2009, 309 (12) :3767-3773