  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\geq1$ be an integer and $\psi$ is a labeling function
(anti-$k$-labeling) from $V(G)$ to $\{1,2,\cdots,k\}$ for a graph $G$. A {\em
no-hole anti-$k$-labeling} is an anti-$k$-labeling using all labels between 1
and $k$. We define $w_{\psi}(e)=|\psi(u)-\psi(v)|$ for an edge $e=uv$ and
$w_{\psi}(G)=\min\{w_{\psi}(e):e\in E(G)\}$ for an anti-$k$-labeling $\psi$ of
the graph $G$. {\em The anti-$k$-labeling number} of a graph $G$, $mc_k(G)$ is
$\max\{w_{\psi}(G): \psi\}$. In this paper, we first show that $mc_k(G)=\lfloor
\frac{k-1}{\chi-1}\rfloor$, and the problem that determines $mc_k(G)$ of graphs
is NP-hard. We mainly obtain the lower bounds on no-hole anti-$n$-labeling
number for trees, grids and $n$-cubes.
