Covering, Packing and Generalized Perfection
Gerard J. Chang, George L. Nemhauser · SIAM Journal on Algebraic and Discrete Methods · 1985
Given a graph $G = ( V,E )$, let $T_k = ( V ( T_k ), E ( T_k ) )$ be a tree of diameter $\leqq k$ that is a partial graph of G. Let $\mathcal{J}_k $ be the set of $V ( T_k )$ for all such G. $T_k $. We consider covering and packing problems defined with respect to G. $\mathcal{J}_k $, for all integers $k\geqq 1$. $\theta ( G:\mathcal{J}_k )$ is the minimum number of elements of $\mathcal{J}_k $ that cover V, and $\alpha ( G:\mathcal{J}_k )$ is the maximum size of a $P \subseteq V$ such that no element of $\mathcal{J}_k $ contains more than one element of P. In particular, $\theta ( G:\mathcal{J}_1 )$ is the edge covering number of G, $\theta ( G:\mathcal{J}_2 )$ is the domination number of G, and $\alpha ( G:\mathcal{J}_1 )$ is the stability number of G. We study classes of chordal graphs for which $\theta ( H:\mathcal{J}_k ) = \alpha ( H:\mathcal{J}_k )$ for all induced subgraphs H of G. We also give simple algorithms for solving these problems on some classes of graphs. These results are applicable to location problems.