论文标题
网格和定向图的邻接和广播维度
Adjacency and Broadcast Dimension of Grid and Directed Graphs
论文作者
论文摘要
令$ g $为简单的无向图。 a函数$ f：v（g）\ to \ mathbb {z} _ {\ geq 0} $是$ \ textit {nesolving brotivcast} $ $ g $ of $ g $，如果对于任何不同的$ x，y \ in v（g）$，则存在a vertex $ z \ in v in v in v（g）$ f（z）$ f（z） f（z）+1 \} \ neq \ min \ {d（z，y），f（z）+1 \} $。 $ \ textit {广播尺寸} $ $ \ text {bdim}（g）$ g $的$是$ \ sum_ {v \ in v（g）} f（g）} f（v）$上的所有解决方面的广播$ f $ g $。同样，$ \ textIt {acecacency dimension} $ $ \ text {adim}（g）$ g $的$是$ \ sum_ {v \ in v（g）} f（g）} f（g）} f（g）} f（g）} f（v）$ by所有nesolving广播$ f $ g $ g $ f $ f $ f $ f $ where $ f $ f $ in $ f $ in $ f $ f in $ \ \ \ {0,11 \} $ \ {0,1，v}。这些参数是通过考虑定向距离的有向图的类似定义的。 我们通过获得路径图的某些笛卡尔产品的邻接维度的精确界限，即$ \ text {adim}（p_2 \ square p_n）$和$ \ text {adim}（p_3 \ square p_n）$，部分解决了张问题。此外，我们研究了有向图的邻接和广播维度的行为。首先，我们明确计算有向完整的$ k $ -ary树的邻接维度，其中每个边缘都朝向叶子。接下来，我们证明$ \ text {adim}（\ vec {g}）= \ text {bdim}（\ vec {g}）$ for某些特定的定向树$ \ vec {g} $。此外，我们表明$ \ text {bdim}（g）$可以与$ \ text {bdim}（\ vec {g}）$的指数函数一样大，也可以像$ \ text {bdim}（bdim}（bdim}（bdim}（\ vec {g}））$的对数函数一样小。
Let $G$ be a simple undirected graph. A function $f : V(G) \to \mathbb{Z}_{\geq 0}$ is a $\textit{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 \} \neq \min \{ d(z, y), f(z)+1 \}$. The $\textit{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 $\textit{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})$.
