Optimal radio-k-labelings of trees

Abstract Let G be a graph, and let k be a positive integer. The radio- k -number of G is the smallest integer s for which there exists a function f : V ( G ) → { 0 , 1 , 2 , … , s } such that for any two vertices u , v ∈ V ( G ) , | f ( u ) − f ( v ) | ⩾ k + 1 − d ( u , v ) , where d ( u , v ) is the distance between u and v . In particular, when d is the diameter of G , the radio- d -number is called the radio number of G . This article contains four major parts. First, we extend Liu’s lower bound on radio numbers of trees to radio- k -numbers of trees. We call a tree whose radio- k -number is equal to this lower bound a k -lower bound tree. Second, we establish properties of k -lower bound trees, and apply these properties to obtain shorter proofs and generalizations of some known results. Third, we investigate the minimum integer k such that a given tree T is a k -lower bound tree. Fourth, we define the joined union operation on trees, where trees are composed by merging a vertex from each tree into a single vertex. We use this operation to construct new k -lower bound trees in three ways. Finally, we pose several questions for future study.