论文标题
两条树木的无线电标签
Radio labelling of two-branch trees
论文作者
论文摘要
图$ g $的无线电标签是映射$ f：v（g）\ rightarrow \ {0，1，2，\ ldots \} $，这样$ | f（u）-f（v）| \ geq diam（g） + 1 -d（u，v）$对于每对不同的顶点$ u，v $ o $ g $，其中$ diam（g）$是$ g $和$ d（u，v）$的直径是$ u $和$ v $ in $ g $ in $ g $之间的距离。无线电编号$ rn（g）$ g $是最小的整数$ k $，因此$ g $允许带有$ \ max \ {f（v）的无线电标签$ f $：v \ in v（g）\} = k $。从V（t）$中的顶点$ v \中的树$ t $的重量是从$ v $到所有其他顶点$ t $中的距离之和，而达到最小重量的顶点称为$ t $的权重中心。众所周知，任何树都有一个或两个重量中心。如果去除其所有重量中心，则一棵树称为两条树木。在本文中，我们获得了两条树木的无线电数量的急剧下限，该界限改善了已知的一般树木下限。我们还为改进的下限提供了必要和充分的条件。使用这些结果，我们确定了两个层次的普通两分支树的无线电数量。
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.
