Domination and packing in graphs
<|reference_start|>Domination and packing in graphs: Given a graph~$G$, the domination number, denoted by~$\gamma(G)$, is the minimum cardinality of a dominating set in~$G$. Dual to the notion of domination number is the packing number of a graph. A packing of~$G$ is a set of vertices whose pairwise distance is at least three. The packing number~$\rho(G)$ of~$G$ is the maximum cardinality of one such set. Furthermore, the inequality~$\rho(G) \leq \gamma(G)$ is well-known. Henning et al.\ conjectured that~$\gamma(G) \leq 2\rho(G)+1$ if~$G$ is subcubic. In this paper, we progress towards this conjecture by showing that~${\gamma(G) \leq \frac{120}{49}\rho(G)}$ if~$G$ is a bipartite cubic graph. We also show that $\gamma(G) \leq 3\rho(G)$ if~$G$ is a maximal outerplanar graph, and that~$\gamma(G) \leq 2\rho(G)$ if~$G$ is a biconvex graph. Moreover, in the last case, we show that this upper bound is tight.<|reference_end|>
@article{gómez2024domination,
    title={Domination and packing in graphs},
    author={Renzo G'omez and Juan Guti'errez},
    journal={arXiv preprint arXiv:2402.05088},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.05088},
    primaryClass={math.CO cs.DM}
}