2023/08/09 by Das, Sandip, Islam, Sk Samim · 1 citation
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2308.04882
For a graph G, mp(G) is the multipacking number, and γb(G) is the broadcast domination number. It is known that mp(G)≤ γb(G) and γb(G)≤ 2mp(G)+3 for any graph G, and it was shown that γb(G)-mp(G) can be arbitrarily large for connected graphs. It is conjectured that γb(G)≤ 2mp(G) for any general graph G. We show that, for any cactus graph G, γb(G)≤ (3)/(2)mp(G)+(11)/(2). We also show that γb(G)-mp(G) can be arbitrarily large for cactus graphs and asteroidal triple-free graphs by constructing an infinite family of cactus graphs which are also asteroidal triple-free graphs such that the ratio γb(G)/mp(G)=4/3, with mp(G) arbitrarily large. This result shows that, for cactus graphs, the bound γb(G)≤ (3)/(2)mp(G)+(11)/(2) cannot be improved to a bound in the form γb(G)≤ c1⋅ mp(G)+c2, for any constant c1<4/3 and c2. Moreover, we provide an O(n)-time algorithm to construct a multipacking of cactus graph G of size at least (2)/(3)mp(G)-(11)/(3) , where n is the number of vertices of the graph G. The hyperbolicity of the cactus graph class is unbounded. For 0-hyperbolic graphs, mp(G)=γb(G). Moreover, mp(G)=γb(G) holds for the strongly chordal graphs which is a subclass of (1)/(2)-hyperbolic graphs. Now it's a natural question: what is the minimum value of δ, for which we can say that the difference γb(G) - mp(G) can be arbitrarily large for δ-hyperbolic graphs? We show that the minimum value of δ is (1)/(2) using a construction of an infinite family of cactus graphs with hyperbolicity (1)/(2).