On the Relationships between Domination, Isolation, and Packing

Abstract

We consider the relationships between the domination number of graph, denoted ${\hat{I}}^3$, and the distance-$2$ domination number, denoted ${\hat{I}}_2^3$, and three parameters that lie between them: the packing number, denoted $\ddot{I}$, the lower packing number, denoted $\ddot{I}{}_L$, and the isolation number, denoted ${\hat{I}}^1$. There has been recent attention on the question of whether ${\hat{I}}^3/\ddot{I}$ is bounded or unbounded for various families of graphs. We consider similar questions for the ratios of the five parameters. In particular we show that, while ${\hat{I}}^3/\ddot{I}{}_L$ is unbounded in trees, it holds that ${\hat{I}}^1/{\hat{I}}_2^3$ is less than $2$ for all trees. Further, ${\hat{I}}^3/\ddot{I}{}_L$ is at most $3$ in interval graphs, at most~$4$ in permutation graphs, and at most $5$ in general asteroidal-triple-free graphs. We also show that every tree has a set of vertices that is both isolating and a packing, and characterize trees where $\ddot{I}=\ddot{I}{}_L$.