Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650738 | Discrete Mathematics | 2008 | 12 Pages |
Abstract
Let G be a connected graph with diameter diam(G)diam(G). The radio number for G , denoted by rn(G)rn(G), is the smallest integer k such that there exists a function f:V(G)→{0,1,2,…,k}f:V(G)→{0,1,2,…,k} with the following satisfied for all vertices u and vv: |f(u)-f(v)|⩾diam(G)-dG(u,v)+1,|f(u)-f(v)|⩾diam(G)-dG(u,v)+1, where dG(u,v)dG(u,v) is the distance between u and vv. We prove a lower bound for the radio number of trees, and characterize the trees achieving this bound. Moreover, we prove another lower bound for the radio number of spiders (trees with at most one vertex of degree more than two) and characterize the spiders achieving this bound. Our results generalize the radio number for paths obtained by Liu and Zhu.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daphne Der-Fen Liu,