Broadcast Dimension of Graphs

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}$\mathrm{.}Afunction$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)$\mathrm{.}Thebroadcastdimension,$bdim(G)$,of$G$istheminimumof$c_f(G)=\sum_{v \in V(G)} f(v)$overallresolvingbroadcastsof$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)=\mathrm{\Omega }(\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.