Relations between packing and covering numbers of a tree

A. Meir and John W. Moon

Vol. 61 (1975), No. 1, 225–233

DOI: 10.2140/pjm.1975.61.225

Abstract

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 that P_2k = C_k.

Mathematical Subject Classification 2000

Primary: 05C05

Milestones

Received: 11 November 1974

Revised: 22 February 1975

Published: 1 November 1975