2022/08/23 by Rachana Madhukara, Madhukara, Rachana
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2208.11001
openalex publication_date 2022/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a simple undirected graph. A function f : V(G) → ℤ≥ 0 is a resolving broadcast of G if for any distinct x, y ∈ V(G), there exists a vertex z ∈ V(G) with f(z) > 0 such that min \ d(z, x), f(z)+1 \ ≠ min \ d(z, y), f(z)+1 \. The broadcast dimension bdim(G) of G is the minimum of ∑v ∈ V(G) f(v) over all resolving broadcasts f of G. Similarly, the adjacency dimension adim(G) of G is the minimum of ∑v ∈ 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 adim(P2 \square Pn) and adim(P3 \square Pn). 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 adim(G) = bdim(G) for some particular directed trees G. Furthermore, we show that bdim(G) can be as large as an exponential function of bdim(G) or as small as a logarithmic function of bdim(G).