Anti-k-labeling of graphs

It is well known that the labeling problems of graphs arise in many (but not limited to) networking and telecommunication contexts. In this paper we introduce the anti-k-labeling problem of graphs which we seek to minimize the similarity (or distance) of neighboring nodes. For example, in the fundamental frequency assignment problem in wireless networks where each node is assigned a frequency, it is usually desirable to limit or minimize the frequency gap between neighboring nodes so as to limit interference. Let k ≥ 1 be an integer and ψ is a labeling function (anti-k-labeling) from V(G) to {1,2,…,k} for a graph G. A no-hole anti-k-labeling is an anti-k-labeling using all labels between 1 and k. We define w_ψ(e)=|ψ(u)−ψ(v)| for an edge e=uv and w_ψ(G)=min{w_ψ(e):e∈E(G)} for an anti-k-labeling ψ of the graph G. The anti-k-labeling number of a graph G, λ_k(G), is max {w_ψ(G): ψ}. In this paper, we first show that λ_k(G)=⌊ [Formula presented] ⌋, and the problem that determines the anti-k-labeling number of graphs is NP-hard. We mainly obtain the lower bounds on no-hole anti-n-labeling number for trees, grids and n-cubes.