论文标题
图形的最佳无线电标签
Optimal radio labelings of graphs
论文作者
论文摘要
令$ \ mathbb {n} $为正整数集。图$ g $的无线电标签是映射$φ：v（g）\ rightarrow \ mathbb {n} \ cup \ {0 \} $，使得不等式$ |φ（u）-φ（v）| \ geq diam（g） + 1 -d（u，v）$均保留每对不同的顶点$ u，v $的$ g $，其中$ diam（g）$和$ d（u，v）$是$ g $和$ u $和$ u $和$ v $ in $ g $的直径。 $ g $的无线电编号$ rn（g）$是最小的$ k $，因此$ g $具有$ \ max \ {φ（v）的无线电标签$φ$：v \ in v（g）\} $ = $ k $。 Das等。 [离散数学。 $ \ mathbf {340} $（2017）855-861]提供了一种为无线电编号找到下限的技术。在[算法和离散应用数学：CALDAM 2019，计算机科学$ \ Mathbf {11394} $，Springer，Cham，2019，161-173]中，修改了这项技术，以找到改进的无线电数，并提供了必要的较低限制，并获得了必要的较低限制，以获得必要的下限，以实现较低的条件。在本文中，给出了一个更有用的必要条件，以实现改进的图形无线电数的改进的下限。使用此结果，确定了路径和车轮图的笛卡尔产品的无线电数。
Let $\mathbb{N}$ be the set of positive integers. A radio labeling of a graph $G$ is a mapping $φ: V(G) \rightarrow \mathbb{N} \cup \{0\}$ such that the inequality $|φ(u)-φ(v)| \geq diam(G) + 1 - d(u,v)$ holds for every pair of distinct vertices $u,v$ of $G$, where $diam(G)$ and $d(u,v)$ are the diameter of $G$ and distance between $u$ and $v$ in $G$, respectively. The radio number $rn(G)$ of $G$ is the smallest number $k$ such that $G$ has radio labeling $φ$ with $\max\{φ(v) : v \in V(G)\}$ = $k$. Das et al. [Discrete Math. $\mathbf{340}$(2017) 855-861] gave a technique to find a lower bound for the radio number of graphs. In [Algorithms and Discrete Applied Mathematics: CALDAM 2019, Lecture Notes in Computer Science $\mathbf{11394}$, springer, Cham, 2019, 161-173], Bantva modified this technique for finding an improved lower bound on the radio number of graphs and gave a necessary and sufficient condition to achieve the improved lower bound. In this paper, one more useful necessary and sufficient condition to achieve the improved lower bound for the radio number of graphs is given. Using this result, the radio number of the Cartesian product of a path and a wheel graphs is determined.
