On packing and covering numbers of graphs (Q1185083)

A subset \(I\subseteq V(G)\) is a \(k\)-packing of \(G\) if \(d(u,v)>k\) for every pair of distinct vertices \(u\) and \(v\) of \(I\). The \(k\)-packing number of \(G\) is the number \(\alpha_ k(G)\) of vertices in any maximum \(k\)-packing of \(G\). A subset \(C\subseteq V(G)\) is a \(k\)-covering of \(G\) if \(d(u,C)\leq k\) for every vertex. The \(k\)-covering number of \(G\) is the number \(\gamma_ k(G)\) of vertices in any minimum \(k\)-covering of \(G\). These invariants were first introduced for trees by \textit{A. Meir} and \textit{J. W. Moon} [Pac. J. Math. 61, 225-233 (1975; Zbl 0289.05101)]. The authors characterize connected graphs of order \((k+1)n\) with \(\gamma_ k=n\), characterize trees with \(\gamma_ k=\alpha_ k\) and show that if \(G\) is a block graph then \(\alpha_ k(G)\) is the smallest integer \(n\) for which there exists a partition of \(V(G)\) into \(n\) subsets each of which induces a subgraph with diameter at most \(k\).