Relation between broadcast domination and multipacking numbers on chordal and other hyperbolic graphs

Abstract

For a graph $G=(V,E)$ with a vertex set $V$ and an edge set $E$, a function $f:V\to \{0,1,2,...,diam(G)\}$ is called a \emph{broadcast} on $G$. For each vertex $u\in V$, if there exists a vertex $v$ in $G$ (possibly, $u=v$) such that $f(v)>0$ and $d(u,v)\le f(v)$, then $f$ is called a dominating broadcast on $G$. The cost of the dominating broadcast $f$ is the quantity ${\sum }_{v\in V}f(v)$. The minimum cost of a dominating broadcast is the broadcast domination number of $G$, denoted by ${\hat{I}}_b^3(G)$. A multipacking is a set $S\subseteq V$ in a graph $G=(V,E)$ such that for every vertex $v\in V$ and for every integer $r\ge 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$, ${\hat{I}}_b^3(G)\le \lceil \frac{3}{2}mp(G)\rceil$. We also show that ${\hat{I}}_b^3(G)-mp(G)$ can be arbitrarily large for connected chordal graphs by constructing an infinite family of connected chordal graphs such that the ratio ${\hat{I}}_b^3(G)/mp(G)=10/9$, with $mp(G)$ arbitrarily large. Moreover, we show that ${\hat{I}}_b^3(G)\le \lfloor \frac{3}{2}mp(G)+2\hat{I}´\rfloor$ holds for all $\hat{I}´$-hyperbolic graphs. In addition, we provide a polynomial-time algorithm to construct a multipacking of a $\hat{I}´$-hyperbolic graph $G$ of size at least $\lceil \frac{2mp(G)-4\hat{I}´}{3}\rceil$.

arXiv admin note: text overlap with arXiv:2308.04882