Safe labeling of graphs with minimum span

Let G be a graph of n vertices and k be a positive integer. We wish to label the vertices of G with positive integers such that each vertex receives a distinct integer and the difference of the labels of two adjacent vertices in G is at least k. We call such a labeling of G a k-safe labeling of G. We call the range from the smallest to the largest integers assigned to the vertices of G in a k-safe labeling the span of the k-safe labeling. The k-safe labeling problem asks to find a k-safe labeling of a graph with the minimum span. In this paper we show that the k-safe labeling problem is NP-hard. We also give upper bounds on k - safe labelings of trees, bipartite graphs, cycles and cactus graphs. Our proofs for upper bounds lead to linear algorithms for finding those labelings.