You are an expert at summarizing long articles. Proceed to summarize the following text: 
we consider simple undirected graphs , and are interested in the classical packings of graphs as introduced in @xcite , and their generalization , called limited packings , as presented in @xcite . in the literature , the classical packings can be referred to under different names , e.g. , as ( distance ) @xmath9-packings @xcite , closed neighborhood packings @xcite , or strong stable sets @xcite . they can also be considered as generalizations of independent ( stable ) sets , which would be ( distance ) @xmath10-packings , following the terminology of @xcite . a vertex set @xmath0 in a graph @xmath1 is a _ @xmath2-limited packing _ if for any vertex @xmath3 , @xmath4 \cap x\right| \le k$ ] , where @xmath5 $ ] is the closed neighbourhood of @xmath6 . @xmath2-limited packing number _ @xmath7 of a graph @xmath1 is the maximum size of a @xmath2-limited packing in @xmath1 . in these terms , the classical ( distance ) @xmath9-packings are @xmath10-limited packings , and hence @xmath11 , where @xmath12 is the 2-packing number . @xmath9-packings ( @xmath10-limited packings ) are well - studied in the literature ( e.g. , @xcite ) . also , several papers discuss connections between packings and dominating sets in graphs ( e.g. , @xcite ) . notice that the corresponding problems have a very different nature : one of the problems ( packings ) is a maximization problem not to break some ( security ) constraints , and the other is a minimization problem ( dominating sets ) to satisfy some reliability requirements . for example , given a graph @xmath1 , the definitions imply a simple inequality @xmath13 , where @xmath14 is the domination number of @xmath1 ( e.g. , see @xcite ) . however , the difference between @xmath12 and @xmath14 can be arbitrarily large . in general , the problems of packings in graphs can be viewed as facility location problems subject to some ( security ) constraints . the problem of finding a @xmath9-packing ( @xmath10-limited packing ) of maximum size is shown to be @xmath8-complete in @xcite . in @xcite , it is shown that the problem of finding a maximum size @xmath2-limited packing is @xmath8-complete even in split or bipartite graphs . we develop the probabilistic method for @xmath2-limited packings and , in particular , for @xmath9-packings ( @xmath10-limited packings ) , with a comparison to a greedy approach . we present two new lower bounds for the @xmath2-limited packing number @xmath7 , and a randomized algorithm to find @xmath2-limited packings satisfying the lower bounds . also , using a greedy algorithm approach , we provide an improved lower bound for @xmath11 . it can be shown that the main lower bound is asymptotically sharp , and the improvements for @xmath10-limited packings from the greedy algorithm approach are asymptotically irrelevant for almost all graphs . we also provide some new upper bounds for @xmath7 . details for some of these results can be found in @xcite . denote by @xmath15 = @xmath16 the maximum vertex degree of @xmath1 , and put @xmath17 . notice that @xmath18 for @xmath19 . we put @xmath20 . the following theorem gives a new lower bound for the @xmath2-limited packing number . [ th1 ] for any graph @xmath1 of order @xmath21 with @xmath22 , @xmath23    the probabilistic construction used to prove theorem [ th1 ] implies a randomized algorithm to find a @xmath2-limited packing set , whose size satisfies bound ( [ main_bound ] ) with a positive probability . a pseudocode presented in algorithm [ alg : k - limited ] below explicitly describes the randomized algorithm . algorithm [ alg : k - limited ] can be implemented to run in @xmath24 time . also , it can be implemented in parallel or as a local distributed algorithm , which is important in some applications . [ alg : k - limited ]    the lower bound of theorem [ th1 ] can be written in a simple weaker form as follows :    for any graph @xmath1 of order @xmath21 , @xmath25    in the case @xmath26 , theorem [ th1 ] gives the following lower bound :    [ cor22 ] for any graph @xmath1 of order @xmath21 with @xmath27 , @xmath28    let @xmath29 = @xmath30 denote the minimum vertex degree of @xmath1 . the lower bound ( [ bcor22 ] ) can be improved as follows :    [ th22 ] for any graph @xmath1 of order @xmath21 , @xmath31    the proof of theorem [ th22 ] provides a greedy algorithm to find a distance @xmath9-packing ( @xmath10-limited packing ) satisfying bound ( [ greedy_bound ] ) . however , as explained later , the lower bound of theorem [ th22 ] is as good as lower bound ( [ bcor22 ] ) of corollary [ cor22 ] for almost all graphs . refining and developing the ideas and techniques used in the proofs of the above results , we have been able to show the following more subtle results . [ tha ] for any graph @xmath1 of order @xmath21 , with vertex degrees @xmath32 , @xmath33 , @xmath34    [ thb ] for any @xmath15-regular graph @xmath1 of order @xmath21 , @xmath35 , @xmath36 the lower bound of theorem [ th1 ] is asymptotically best possible for some ` large ' values of @xmath2 . bound ( [ main_bound ] ) can be written as @xmath37{{\delta \choose k } ( \delta + 1 ) } } $ ] for @xmath38 . combining this with the upper bound of lemma @xmath39 from @xcite , for any connected graph @xmath1 with @xmath40 , we have : @xmath41{{\delta \choose k } ( \delta + 1 ) } } \times { k \over k+1 } n   \;\le\ ; l_k(g)\ ; \le \;{k \over k+1 } n.\ ] ] notice that the upper bound in the inequality ( [ ineq5 ] ) is sharp ( see @xcite ) , and bounds ( [ ineq5 ] ) provide an interval of possible values for @xmath7 in terms of @xmath2 and @xmath15 ( when @xmath42 ) . for regular graphs , @xmath43 , and , when @xmath44 , we have @xmath45{{\delta \choose k } ( \delta + 1 ) } } =   { 1 \over \left(k+1\right)^{1/k } } \longrightarrow 1\ \quad\mbox{as } \quad \ k \to \infty$ ] . therefore , theorem [ th1 ] is asymptotically sharp for regular connected graphs in the case @xmath44 . a similar statement can be proved when @xmath46 . thus , the following result is true :      as stated in theorem [ th22 ] , in contrast to the situation for relatively ` large ' values of @xmath2 , bound ( [ main_bound ] ) of theorem [ th1 ] ( corollary [ cor22 ] ) can be improved for distance @xmath9-packings ( @xmath10-limited packings ) , i.e. when @xmath26 . however , this improvement is irrelevant for almost all graphs . a @xmath10-limited packing set @xmath0 in @xmath1 has a very strong property that any two vertices of @xmath0 are at distance at least @xmath48 in @xmath1 . it is well known that almost every graph has diameter equal to @xmath9 . therefore , @xmath49 for almost all graphs . thus , in the case @xmath26 , theorem [ th1 ] yields a lower bound of 1 for almost all graphs and is as good as theorem [ th22 ] . notice that the bound of theorem [ th22 ] is sharp , for example for any number of disjoint copies of the petersen graph . when @xmath1 has a diameter larger than @xmath9 , it should be better to use the greedy algorithm and lower bound ( [ greedy_bound ] ) provided by theorem [ th22 ] : it improves bound ( [ bcor22 ] ) of corollary [ cor22 ] by a factor of @xmath50 .    as mentioned earlier , @xmath51 . in @xcite , the authors provide several upper bounds for @xmath7 , e.g. , given any graph @xmath1 , @xmath52 . considering the @xmath2-tuple domination number @xmath53 and results of @xcite , it is possible to prove the following upper bounds for @xmath7 . a set @xmath0 is a _ @xmath2-tuple dominating set _ of @xmath1 if for every vertex @xmath3 , @xmath54\cap x|\ge k$ ] . the minimum cardinality of a @xmath2-tuple dominating set of @xmath1 is the _ @xmath2-tuple domination number _ @xmath53 . the @xmath2-tuple domination number is only defined for graphs with @xmath55 . in @xcite , we define @xmath56 and , for @xmath57 , @xmath58 . a. gagarin , v. zverovich , the probabilistic approach to limited packings in graphs , corr abs/1311.1707 ( 2013 ) . r. gallant , g. gunther , b. hartnell , d. rall , limited packings in graphs , _ discrete appl . math . _ * 158*(12 ) ( 2010 ) 13571364 .
we consider ( closed neighbourhood ) packings and their generalization in graphs called limited packings . 
 a vertex set @xmath0 in a graph @xmath1 is a _ @xmath2-limited packing _ 
 if for any vertex @xmath3 , @xmath4 \cap x\right| \le k$ ] , where @xmath5 $ ] is the closed neighbourhood of @xmath6 . 
 the _ @xmath2-limited packing number _ 
 @xmath7 is the largest size of a @xmath2-limited packing in @xmath1 . 
 limited packing problems can be considered as secure facility location problems in networks . 
 we develop probabilistic and greedy approaches to limited packings in graphs , providing lower bounds for the @xmath2-limited packing number , and randomized and greedy algorithms to find @xmath2-limited packings satisfying the bounds . 
 some upper bounds for @xmath7 are given as well . 
 the problem of finding a maximum size @xmath2-limited packing is known to be @xmath8-complete even in split or bipartite graphs .