The probabilistic approach to limited packings in graphs

Zverovich, Vadim; Gagarin, Andrei

Abstract

© 2014 Elsevier B.V. All rights reserved. We consider (closed neighbourhood) packings and their generalization in graphs. A vertex set X in a graph G is a k-limited packing if for every vertex vεV(G), |N[v]∩X|≤k, where N[v] is the closed neighbourhood of v. The k-limited packing number (G) of a graph G is the largest size of a k-limited packing in G. Limited packing problems can be considered as secure facility location problems in networks. In this paper, we develop a new application of the probabilistic method to limited packings in graphs, resulting in lower bounds for the k-limited packing number and a randomized algorithm to find k-limited packings satisfying the bounds. In particular, we prove that for any graph G of order n with maximum vertex degree δ,(G)≥kn(k+1)(δk)(δ+1)k. Also, some other upper and lower bounds for (G) are given.

• Journal Article Type: Article
• Publication Date: Jan 1, 2015
• Publicly Available Date: Jun 6, 2019
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 184
• Pages: 146-153
• DOI: https://doi.org/10.1016/j.dam.2014.11.017
• Keywords: k-limited packings, the probabilistic method, lower and upper bounds, randomized algorithm
• Public URL: https://uwe-repository.worktribe.com/output/836953
• Publisher URL: http://dx.doi.org/10.1016/j.dam.2014.11.017