论文标题
两棵树的笛卡尔产品的无线电编号
Radio Number for the Cartesian Product of Two Trees
论文作者
论文摘要
令$ g $为简单的连接图。对于任何两个顶点$ u $和$ v $，让$ d（u，v）$表示$ g $中的$ u $和$ v $之间的距离，让$ diam（g）$表示$ g $的直径。 $ g $的无线电标签是一个函数$ f $，它为每个顶点分配一个非负整数（标签），因此对于每个不同的顶点$ u $和$ g $中的$ v $ \ geq diam（g）-d（u，v） +1 $。 $ f $的跨度是$ f（v）$的最大和最小标签之间的差异。 $ g $的无线电编号，用$ rn（g）$表示，是$ g $接收的广播标签的最小跨度。在本文中，我们为两棵树的笛卡尔产品的无线电数提供了一个下限。此外，我们提出了三个必要的和充分的条件，并为两棵树的乘积提供了三个足够的条件，以实现这一目标。应用这些结果，我们确定了两颗恒星的笛卡尔产品的无线电数，以及一条路径和一条恒星。
Let $G$ be a simple connected graph. For any two vertices $u$ and $v$, let $d(u,v)$ denote the distance between $u$ and $v$ in $G$, and let $diam(G)$ denote the diameter of $G$. A radio-labeling of $G$ is a function $f$ which assigns to each vertex a non-negative integer (label) such that for every distinct vertices $u$ and $v$ in $G$, it holds that $|f(u)-f(v)| \geq diam(G) - d(u,v) +1$. The span of $f$ is the difference between the largest and smallest labels of $f(V)$. The radio number of $G$, denoted by $rn(G)$, is the smallest span of a radio labeling admitted by $G$. In this paper, we give a lower bound for the radio number of the Cartesian product of two trees. Moreover, we present three necessary and sufficient conditions, and three sufficient conditions for the product of two trees to achieve this bound. Applying these results, we determine the radio number of the Cartesian product of two stars as well as a path and a star.
