کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647156 | 1342330 | 2015 | 9 صفحه PDF | دانلود رایگان |
We study vertex labelings φ:V→{0,1,2,…}φ:V→{0,1,2,…} of a graph G=(V,E)G=(V,E) which assign nonnegative integers to the vertices and the restrictions depend on the distances in GG. Fixing a positive integer dd, the requirement is that if vertices uu and vv are at distance ii apart (where 1≤i≤d1≤i≤d), then |φ(u)−φ(v)|>d−i|φ(u)−φ(v)|>d−i must hold. A corollary of the main result of this paper is an exact formula for the smallest possible value of maxv∈Vφ(v)maxv∈Vφ(v) for trees whose internal vertices all have the same degree and all leaves are at distance d/2d/2 from the central vertex (for dd even) or at distance (d−1)/2(d−1)/2 from the central edge (for dd odd). The case of even diameter extends the main theorem of Li et al. (2010) on complete rooted trees with fixed down-degree and height.
Journal: Discrete Mathematics - Volume 338, Issue 8, 6 August 2015, Pages 1398–1406