Total Labelling of the Tree

Abstract:

. The (2,1)-total labelling of the tree has been widely studied. In this paper we study the (3,1)-total labelling number of the tree. The (3,1)-total labelling number of the tree is the width of the smallest range of integers to label the vertices and the edges such that no two adjacent vertices or two adjacent edges have the same labels and the difference between the labels of a vertex and its incident edges is at least 3. We prove that if the distance of the maximum degree in the tree is not 2, then the (3,1)-total labelling number is the maximum degree plus 3.

• Periodical: Applied Mechanics and Materials (Volumes 105-107)
• Pages: 2275-2278
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.105-107.2275
• Online since: September 2011
• Authors: Hai Na Sun
• Keywords: Degree, Handle, Tree

References

[1] W. K. Hale, Frequency assignment: theory and applications, Proc IEEE 68(1980), 1497-1514.

DOI: 10.1109/proc.1980.11899

[2] J. R. Griggs and R. K. Yeh, Labelling graphs with a condition at distance 2,SIAM J Discrete Math 5(1992), pp.586-595.

DOI: 10.1137/0405048

[3] G. J. Chang and D. Kuo, The labelling problem on graphs, SIAM J Discrete Math 9(1996), pp.309-316.

[4] G. J. Chang, W.-T. Ke, D. Kuo, Daphne D.-F. Liu, and R. K. Yeh, On labelling of graphs, Discrete Math 220(2000), pp.57-66.

[5] J. P. Georges, D. W. Mauro, and M. I. Stein, Labeling products of complete graphs with a condition at distance two, SIAM J Discrete Math 14(2000), pp.28-35.

DOI: 10.1137/s0895480199351859

[6] D. Kr'al and R. ˇSkrekovski, A theorem about the channel assignment problem, SIAM J Discrete Math 16(2003), pp.426-437.

DOI: 10.1137/s0895480101399449

[7] M. Molloy and M. R. Salavatipour, A bound on the chromatic number of the square of a planar graph, J Combin Theory Ser B 94(2005), pp.189-213.

DOI: 10.1016/j.jctb.2004.12.005

[8] D. Sakai, Labelling chordal graphs: distance two condition, SIAM J Discrete Math 7(1994), pp.133-140.

DOI: 10.1137/s0895480191223178

[9] W. Wang and K.-W. Lih, Labelling planar graphs with conditions on girth and distance two, SIAM J Discrete Math 17(2004), pp.264-275.

DOI: 10.1137/s0895480101390448

[10] W. Wang, The labelling of trees, Discrete Applied Math 154(2006), pp.598-603.

[11] M. A. Whittlesey, J. P. Georges, and D. W. Mauro, On the number of Qn and related graphs, SIAM J Discrete Math 8(1995), pp.499-506.

DOI: 10.1137/s0895480192242821

[12] F. Havet, total labelling of graphs, Workshop on Graphs and Algorithms,Dijon, France (2003).

[13] F. Havet and M.-L. Yu, total labelling of graphs, Discrete Math, in press.

[14] O. V. Borodin, A. V. Kostochak, and D. R. Woodall, List edge and list total coloring of multigraphs, J Combin Theory Ser B 71(1997), pp.184-204.

DOI: 10.1006/jctb.1997.1780

[15] A. V. Kostochka, The total chromatic number of any multigraph with maximum degree five is at most seven, Discrete Math 162(1996), pp.199-214.

DOI: 10.1016/0012-365x(95)00286-6

[16] M. Molloy and B. Reed, A bound on the total chromatic number, Combinatorics 18(1998), pp.241-280.

[17] W. Wang, Total chromatic number of planar graphs with maximum degree ten, J Graph Theory 54(2007), pp.91-102.

DOI: 10.1002/jgt.20195

[18] K.-W. Lih, Daphne D.-F. Liu, and W. Wang, A generalized total coloring of graphs, preprint, 2005.

[19] F. Bazzaroa, M. Montassier, and A. Raspaud, total labelling of planar graphs with large girth and high maximum degree, Discrete Math, in press.

[20] D. Chen and W. Wang, total labelling of outerplanar graphs, submitted.

[21] M. Montassier and A. Raspaud, -total labelling of graphs with a given maximum average degree, J Graph Theory 51(2006), pp.93-109.

DOI: 10.1002/jgt.20124

[22] Jing Huang, Haina Sun and Weifan Wang: (2,1)-totalling of trees with sparse vertices of maximum degree, Information Processing Letters. Vol 3(109), 2009. pp.199-203.

DOI: 10.1016/j.ipl.2008.10.001