کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421118 | 684142 | 2015 | 8 صفحه PDF | دانلود رایگان |
We consider (closed neighbourhood) packings and their generalization in graphs. A vertex set XX in a graph GG is a kk-limited packing if for every vertex v∈V(G)v∈V(G), |N[v]∩X|≤k|N[v]∩X|≤k, where N[v]N[v] is the closed neighbourhood of vv. The kk-limited packing number Lk(G)Lk(G) of a graph GG is the largest size of a kk-limited packing in GG. 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 kk-limited packing number and a randomized algorithm to find kk-limited packings satisfying the bounds. In particular, we prove that for any graph GG of order nn with maximum vertex degree ΔΔ, Lk(G)≥kn(k+1)(Δk)(Δ+1)k. Also, some other upper and lower bounds for Lk(G)Lk(G) are given.
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 146–153