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)=⌊k−1χ−1⌋, 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.