Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419543 | Discrete Applied Mathematics | 2010 | 8 Pages |
Abstract
We define a kk-limited packing in a graph, which generalizes a 2-packing in a graph, and give several bounds on the size of a kk-limited packing. One such bound involves the domination number of the graph, and here we show all trees attaining the bound can be built via a simple sequence of operations. We consider graphs where every maximal 2-limited packing is a maximum 2-limited packing, and characterize their structure in a number of cases.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Robert Gallant, Georg Gunther, Bert L. Hartnell, Douglas F. Rall,