کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647156 1342330 2015 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Distance-constrained labeling of complete trees
ترجمه فارسی عنوان
برچسب زدن فاصله از طریق محدودیت درختان کامل
کلمات کلیدی
رنگ آمیزی نمودار، درخت کامل، برچسب زدن در سطح چند سطح، برچسب زدن رادیو، شماره رادیو
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 8, 6 August 2015, Pages 1398–1406
نویسندگان
, ,