论文标题
图表的广播维度
Broadcast Dimension of Graphs
论文作者
论文摘要
在本文中，我们启动了广播维度的研究，这是度量维度的变体。让$ g $是带有顶点套装$ v（g）$的图表，让$ d（u，w）$表示$ u-w $ Geodesic的长度，$ g $。对于$ k \ ge 1 $，让$ d_k（x，y）= \ min \ {d（x，y），k+1 \} $。 A function $f: V(G) \rightarrow \mathbb{Z}^+ \cup \{0\}$ is called a resolving broadcast of $G$ if, for any distinct $x,y \in V(G)$, there exists a vertex $z \in V(G)$ such that $f(z)=i>0$ and $d_{i}(x,z) \neq d_ {i}（y，z）$。 $ g $的广播维度，$ bdim（g）$是$ c_f（g）= \ sum_ {v \ in v（g）} f（g）} f（g）} f（v）$的$ g $，其中$ g $的所有分辨率广播，其中$ c_f（g）可以将$（$ c_f（g）的总成本视为$ $ $ g的总成本（由各种$ G的$ GRAPTION）所描述的整个图形。请注意，如果Jannesari和Omoomi在2012年引入的$ bdim（g）$减少到$ adim（g）$（$ g $的邻接尺寸），如果解决广播的共同点仅限于$ \ \ {0,1 \} $。我们确定其对循环，路径和其他图的家族的价值。我们证明所有图$ g $的$ g $ $ n $的$ bdim（g）=ω（\ log {n}）$，结果是敏锐的，达到了恒定的因素。我们表明$ \ frac {adim（g）} {bdim（g）} $和$ \ frac {bdim（g）} {dim（g）} $都可以任意大，其中$ dim（g）$表示$ g $的度量尺寸。我们还检查了顶点缺失对邻接维度和图形广播维度的影响。
In this paper we initiate the study of broadcast dimension, a variant of metric dimension. Let $G$ be a graph with vertex set $V(G)$, and let $d(u,w)$ denote the length of a $u-w$ geodesic in $G$. For $k \ge 1$, let $d_k(x,y)=\min \{d(x,y), k+1\}$. A function $f: V(G) \rightarrow \mathbb{Z}^+ \cup \{0\}$ is called a resolving broadcast of $G$ if, for any distinct $x,y \in V(G)$, there exists a vertex $z \in V(G)$ such that $f(z)=i>0$ and $d_{i}(x,z) \neq d_{i}(y,z)$. The broadcast dimension, $bdim(G)$, of $G$ is the minimum of $c_f(G)=\sum_{v \in V(G)} f(v)$ over all resolving broadcasts of $G$, where $c_f(G)$ can be viewed as the total cost of the transmitters (of various strength) used in resolving the entire network described by the graph $G$. Note that $bdim(G)$ reduces to $adim(G)$ (the adjacency dimension of $G$, introduced by Jannesari and Omoomi in 2012) if the codomain of resolving broadcasts is restricted to $\{0,1\}$. We determine its value for cycles, paths, and other families of graphs. We prove that $bdim(G) = Ω(\log{n})$ for all graphs $G$ of order $n$, and that the result is sharp up to a constant factor. We show that $\frac{adim(G)}{bdim(G)}$ and $\frac{bdim(G)}{dim(G)}$ can both be arbitrarily large, where $dim(G)$ denotes the metric dimension of $G$. We also examine the effect of vertex deletion on the adjacency dimension and the broadcast dimension of graphs.
