Radio number of trees

详细信息    查看全文

• 作者：Devsi Bantva^a ; ^{devsi.bantva@gmail.com} ; Samir Vaidya^b ; ^{samirkvaidya@yahoo.co.in} ; Sanming Zhou^c ; ^{smzhou@ms.unimelb.edu.au}
• 关键词：Channel assignment ; Radio labeling ; Radio number ; Trees
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：110-122
• 全文大小：827 K
• 卷排序：217

文摘

A radio labeling of a graph GG is a mapping f:V(G)→{0,1,2,…}f:V(G)→{0,1,2,…} such that |f(u)−f(v)|≥diam(G)+1−d(u,v) for every pair of distinct vertices u,vu,v of GG, where diam(G) is the diameter of GG and d(u,v)d(u,v) the distance between uu and vv in GG. The radio number of GG is the smallest integer kk such that GG has a radio labeling ff with max{f(v):v∈V(G)}=kmax{f(v):v∈V(G)}=k. We give a necessary and sufficient condition for a lower bound on the radio number of trees to be achieved, two other sufficient conditions for the same bound to be achieved by a tree, and an upper bound on the radio number of trees. Using these, we determine the radio number for three families of trees.