Multipacking and Broadcast Domination on Cactus Graphs and Its Impact on Hyperbolic Graphs
摘要
For a graph G, \( {{\,\textrm{mp}\,}}(G) \) is the multipacking number, and \(\gamma _b(G)\) is the broadcast domination number. It is known that \({{\,\textrm{mp}\,}}(G)\le \gamma _b(G)\) and \(\gamma _b(G)\le 2{{\,\textrm{mp}\,}}(G)+3\) for any graph G, and it was shown that \(\gamma _b(G)-{{\,\textrm{mp}\,}}(G)\) can be arbitrarily large for connected graphs. It is conjectured that \(\gamma _b(G)\le 2{{\,\textrm{mp}\,}}(G)\) for any general graph G. We show that, for any cactus graph G, \(\gamma _b(G)\le \frac{3}{2}{{\,\textrm{mp}\,}}(G)+\frac{11}{2}\) . Although cactus graphs form a narrow graph class, we used some non-trivial techniques to provide the bound. These techniques make an important step towards generating a tighter bound for general graphs. We also show that \(\gamma _b(G)-{{\,\textrm{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 \(\gamma _b(G)/{{\,\textrm{mp}\,}}(G)=4/3\) , with \({{\,\textrm{mp}\,}}(G)\) arbitrarily large. Moreover, we provide an O(n)-time algorithm to construct a multipacking of cactus graph G of size at least \( \frac{2}{3}{{\,\textrm{mp}\,}}(G)-\frac{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, \({{\,\textrm{mp}\,}}(G)=\gamma _b(G)\) . Moreover, \({{\,\textrm{mp}\,}}(G)=\gamma _b(G)\) holds for the strongly chordal graphs which is a subclass of \(\frac{1}{2}\) -hyperbolic graphs. Now it’s a natural question: what is the minimum value of \(\delta \) , for which we can say that the difference \( \gamma _{b}(G) - {{\,\textrm{mp}\,}}(G) \) can be arbitrarily large for \(\delta \) -hyperbolic graphs? We show that the minimum value of \(\delta \) is \(\frac{1}{2}\) using a construction of an infinite family of cactus graphs with hyperbolicity \(\frac{1}{2}\) .