Vol. 61, No. 1, 1975

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 320: 1
Vol. 319: 1  2
Vol. 318: 1  2
Vol. 317: 1  2
Vol. 316: 1  2
Vol. 315: 1  2
Vol. 314: 1  2
Vol. 313: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Contacts
 
Submission Guidelines
Submission Form
Policies for Authors
 
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
 
Other MSP Journals
Relations between packing and covering numbers of a tree

A. Meir and John W. Moon

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

Let Pk 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 Ck 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 Pk and Ck; in particular, we show that Pk + kCk n if n k + 1 and that P2k = Ck.

Mathematical Subject Classification 2000
Primary: 05C05
Milestones
Received: 11 November 1974
Revised: 22 February 1975
Published: 1 November 1975
Authors
A. Meir
John W. Moon