论文标题
在图表的广播维度上
On the Broadcast Dimension of a Graph
论文作者
论文摘要
一个函数$ f：v（g）\ rightarrow \ mathbb {z}^+ \ cup \ {0 \ {0 \} $是图$ g $的播放，如果对于任何不同的$ x，y \ in v（g）$，则evertex $ z \ in Vertex $ z \ in V in v（g）in $ f（z）$ f（z） f（z）+1 \} \ neq \ min \ {d（y，z），f（z）+1 \}。$ $ g $的广播维度是$ \ sum_ {v \ in v（g）} f（g）} f（g）} f（v）f（v）$ f（v）$ f $ g $ g $ f $ g $。 Geneson和Yi引入了广播维度的概念，作为度量尺寸的变体，并在网络发现和机器人导航等领域具有应用。 在本文中，我们在顶点数量的无环图的广播维度上得出了一个渐近紧密的下限，并且在邻接尺寸的一般图的广播维度上，Geneson和Yi的下限在邻接尺寸的广播维度上是无关的。我们还研究了单个边缘删除下图的广播维度的变化。我们表明，边缘删除下图的广播维度的添加剂增加和减小都是无限的。此外，我们表明，在边缘删除下，任何图的广播维度最多增加3个。这些结果完全回答了Geneson和Yi提出的三个问题。
A function $f:V(G)\rightarrow \mathbb{Z}^+ \cup \{0\}$ is a resolving broadcast of a graph $G$ if, for any distinct $x,y\in V(G)$, there exists a vertex $z\in V(G)$ with $f(z)>0$ such that $\min\{d(x,z), f(z)+1\} \neq \min\{d(y,z), f(z)+1\}.$ The broadcast dimension of $G$ is the minimum of $\sum_{v\in V(G)}f(v)$ over all resolving broadcasts $f$ of $G$. The concept of broadcast dimension was introduced by Geneson and Yi as a variant of metric dimension and has applications in areas such as network discovery and robot navigation. In this paper, we derive an asymptotically tight lower bound on the broadcast dimension of an acyclic graph in the number of vertices, and we show that a lower bound by Geneson and Yi on the broadcast dimension of a general graph in the adjacency dimension is asymptotically tight. We also study the change in the broadcast dimension of a graph under a single edge deletion. We show that both the additive increase and decrease of the broadcast dimension of a graph under edge deletion is unbounded. Moreover, we show that under edge deletion, the broadcast dimension of any graph increases by a multiplicative factor of at most 3. These results fully answer three questions asked by Geneson and Yi.
