2025/07/02 by Deepak Rajendraprasad, Varun Sani, Rajendraprasad, Deepak +5
Computer Science · #Advanced Graph Theory Research #Interconnection Networks and Systems #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2507.01565
For an undirected graph G, a dominating broadcast on G is a function f : V(G) → ℕ such that for any vertex u ∈ V(G), there exists a vertex v ∈ V(G) with f(v) \geqslant 1 and d(u,v) \leqslant f(v). The cost of f is ∑v ∈ V f(v). The minimum cost over all the dominating broadcasts on G is defined as the broadcast domination number γb(G) of G. A multipacking in G is a subset M ⊆ V(G) such that, for every vertex v ∈ V(G) and every positive integer r, the number of vertices in M within distance r of v is at most r. The multipacking number of G, denoted mp(G), is the maximum cardinality of a multipacking in G. These two optimisation problems are duals of each other, and it easily follows that mp(G) \leqslant γb(G). It is known that γb(G) \leqslant 2mp(G)+3 and conjectured that γb(G) \leqslant 2mp(G). In this paper, we show that for the n-dimensional hypercube Qn \lfloor(n)/(2) \rfloor \leqslant mp(Qn) \leqslant (n)/(2) + 6√(2n). Since γb(Qn) = n-1 for all n \geqslant 3, this verifies the above conjecture on hypercubes and, more interestingly, gives a sequence of connected graphs for which the ratio (γb(G))/(mp(G)) approaches 2, a search for which was initiated by Beaudou, Brewster and Foucaud in 2018. It follows that, for connected graphs G \limsupmp(G) → ∞ \(γb(G))/(mp(G))\ = 2. The lower bound on mp(Qn) is established by a recursive construction, and the upper bound is established using a classic result from discrepancy theory.