Adjacency and Broadcast Dimension of Grid and Directed Graphs

Abstract

Let $G$ be a simple undirected graph. A function $f:V(G)\to {\mathbb{Z}}_{\ge 0}$ is a $\text{resolving broadcast}$ of $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(z,x),f(z)+1\}\ne \min \{d(z,y),f(z)+1\}$. The $\text{broadcast dimension}$ $\text{bdim}(G)$ of $G$ is the minimum of ${\sum }_{v\in V(G)}f(v)$ over all resolving broadcasts $f$ of $G$. Similarly, the $\text{adjacency dimension}$ $\text{adim}(G)$ of $G$ is the minimum of ${\sum }_{v\in V(G)}f(v)$ over all resolving broadcasts $f$ of $G$ where $f$ takes values in $\{0,1\}$. These parameters are defined analogously for directed graphs by considering directed distances. We partially resolve a question of Zhang by obtaining precise bounds for the adjacency dimension of certain Cartesian products of path graphs, namely $\text{adim}(P_2\square P_n)$ and $\text{adim}(P_3\square P_n)$. Additionally, we study the behavior of adjacency and broadcast dimension on directed graphs. First, we explicitly calculate the adjacency dimension of a directed complete $k$-ary tree, where every edge is directed towards the leaves. Next, we prove that $\text{adim}(\vec{G})=\text{bdim}(\vec{G})$ for some particular directed trees $\vec{G}$. Furthermore, we show that $\text{bdim}(G)$ can be as large as an exponential function of $\text{bdim}(\vec{G})$ or as small as a logarithmic function of $\text{bdim}(\vec{G})$.

16 pages, 12 figures