solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看11833次
Anti-$k$-labeling of graphs. (arXiv:1810.06984v1 [math.CO])
来源于:arXiv
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 th 查看全文>>