Vol. 61, No. 1, 1975

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 294: 1
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Vol. 289: 1  2
Vol. 288: 1  2
Vol. 287: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
Author Index
To Appear
 
ISSN: 0030-8730
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