A radio labelling of a graph $G$ is a mapping $f : V(G) \rightarrow \{0, 1, 2,\ldots\}$ such that $|f(u)-f(v)| \geq diam(G) + 1 - d(u,v)$ for every pair of distinct vertices $u,v$ of $G$, where $diam(G)$ is the diameter of $G$ and $d(u,v)$ is the distance between $u$ and $v$ in $G$. The radio number $rn(G)$ of $G$ is the smallest integer $k$ such that $G$ admits a radio labelling $f$ with $\max\{f(v):v \in V(G)\} = k$. The weight of a tree $T$ from a vertex $v \in V(T)$ is the sum of the distances in $T$ from $v$ to all other vertices, and a vertex of $T$ achieving the minimum weight is called a weight center of $T$. It is known that any tree has one or two weight centers. A tree is called a two-branch tree if the removal of all its weight centers results in a forest with exactly two components. In this paper we obtain a sharp lower bound for the radio number of two-branch trees which improves a known lower bound for general trees. We also give a necessary and sufficient condition for this improved lower bound to be achieved. Using these results, we determine the radio number of two families of level-wise regular two-branch trees.
翻译:收音标号是图形 $G$ 的映射 $f : V(G) \rightarrow \{0, 1, 2,\ldots\}$,满足每对不同的顶点 $u,v$,都有 $|f(u)-f(v)| \geq diam(G) + 1 - d(u,v)$,其中 $diam(G)$ 是 $G$ 的直径,$d(u,v)$ 是 $u$ 和 $v$ 在 $G$ 中的距离。$G$ 的最大标号为 $k$ 的收音标签 $f$ 存在的条件是,$\max\{f(v):v \in V(G)\} = k$。树 $T$ 中从顶点 $v$ 的权重是从 $v$ 到所有其他顶点的距离之和,到达最小权重的 $T$ 的顶点称为其重心。已知任何树都有一个或两个重心。如果删除所有重心后,一棵树变成了仅有两个连通块的森林,则该树称为二分木。本文给出了二分木收音标号的尖锐下界,该下界优于一般树的已知下界。本文还给出了实现该改进下界的必要和充分条件。利用这些结果,本文确定了两个级别无规则二分木族的收音标号。