Relations between packing and covering numbers of a tree
A. Meir, John W. Moon · Pacific Journal of Mathematics · 1975
Let P k denote the size of the largest subset of nodes of a tree T with n nodes such that the distance between any two nodes in the subset is at least k + 1; let C k denote the size of the smallest subset of nodes of T such that every node of T is at distance at most k from some node in the subset.We determine various relations involving P k and C k ; in particular, we show that P k + kC k ^n if n^k + 1 and that1* Introduction* The distance between nodes x and y in a graph G is the number d(x, y) of edges in any shortest path in G that joins x and y. (For definitions not given here see [1]