2023/12/16 by Das, Sandip, Foucaud, Florent, Islam, Sk Samim +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2312.10485
For a graph G = (V, E) with a vertex set V and an edge set E , a function f : V → \0, 1, 2, . . . , diam(G)\ is called a broadcast on G . For each vertex u ∈ V , if there exists a vertex v in G (possibly, u = v ) such that f (v) > 0 and d(u, v) ≤ f (v) , then f is called a dominating broadcast on G . The cost of the dominating broadcast f is the quantity ∑v∈ Vf(v) . The minimum cost of a dominating broadcast is the broadcast domination number of G, denoted by γb(G) . A multipacking is a set S ⊆ V in a graph G = (V, E) such that for every vertex v ∈ V and for every integer r ≥ 1 , the ball of radius r around v contains at most r vertices of S , that is, there are at most r vertices in S at a distance at most r from v in G . The multipacking number of G is the maximum cardinality of a multipacking of G and is denoted by mp(G) . We show that, for any connected chordal graph G, γb(G)≤ \lceil(3)/(2) mp(G)\rceil. We also show that γb(G)-mp(G) can be arbitrarily large for connected chordal graphs by constructing an infinite family of connected chordal graphs such that the ratio γb(G)/mp(G)=10/9, with mp(G) arbitrarily large. Moreover, we show that γb(G)≤ \lfloor(3)/(2) mp(G)+2δ\rfloor holds for all δ-hyperbolic graphs. In addition, we provide a polynomial-time algorithm to construct a multipacking of a δ-hyperbolic graph G of size at least \lceil(2mp(G)-4δ)/(3) \rceil .