Abstract
The radio k-chromatic number rck(G) of a graph G is the minimum integer λ such that there exists a function ϕ: V(G) → { 0, 1, ⋯, λ} satisfying | ϕ(u) – ϕ(v) | ≥ k+ 1 – d(u, v), where d(u, v) denotes the distance between u and v. To date, several upper and lower bounds of rck(· ) is established for different graph families. One of the most notable works in this domain is due to Liu and Zhu [SIAM Journal on Discrete Mathematics 2005] whose main results were computing the exact values of rck(· ) for paths and cycles for the specific case when k is equal to the diameter. In this article, we find the exact values of rck(G) for powers of paths where the diameter of the graph is strictly less than k. Our proof readily provides a linear time algorithm for providing such labeling. Furthermore, our proof technique is a potential tool for solving the same problem for other graph classes with “small” diameter.