Distance-constrained labeling of complete trees

Halász, Veronika and Tuza, Zsolt (2015) Distance-constrained labeling of complete trees. Discrete Mathematics, 338 (8). pp. 1398-1406. ISSN 0012-365X

Text tuza.pdf Restricted to Registered users only Download (396kB) | Request a copy

Abstract

Abstract We study vertex labelings φ:V → {0,1,2,...} of a graph G=(V,E) which assign nonnegative integers to the vertices and the restrictions depend on the distances in G. Fixing a positive integer d, the requirement is that if vertices u and v are at distance i apart (where 1≤i≤d), then |φ(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) for trees whose internal vertices all have the same degree and all leaves are at distance d/2 from the central vertex (for d even) or at distance (d-1)/2 from the central edge (for d 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. © 2015 Published by Elsevier B.V.

Actions (login required)

Edit Item