2020/05/15 by Jesse Geneson, Geneson, Jesse, Eunjeong Yi +1
Computer Science · Mathematics · #Combinatorics #Combinatorics (math.CO) #Dimension (graph theory) #Discrete Mathematics (cs.DM) #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #Graph #Graph Labeling and Dimension Problems #Line graph #Mathematics #Metric dimension #Omega #Physics #Vertex (graph theory) #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2005.07311
arxiv created 2020/05/15 · openalex publication_date 2020/05/15 · arxiv updated 2020/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ≥ 1, let dk(x,y)=min \d(x,y), k+1\. A function f: V(G) → ℤ+ ∪ \0\ is called a resolving broadcast of G if, for any distinct x,y ∈ V(G), there exists a vertex z ∈ V(G) such that f(z)=i>0 and di(x,z) ≠ di(y,z). The broadcast dimension, bdim(G), of G is the minimum of cf(G)=∑v ∈ V(G) f(v) over all resolving broadcasts of G, where cf(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) = Ω(logn) for all graphs G of order n, and that the result is sharp up to a constant factor. We show that (adim(G))/(bdim(G)) and (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.