2015/01/08 by Paul N. Balister, Béla Bollobás, Balister, Paul N. +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1501.01833
arxiv created 2015/01/08 · arxiv updated 2015/01/09
The k-limited packing number, Lk(G), of a graph G, introduced by Gallant, Gunther, Hartnell, and Rall, is the maximum cardinality of a set X of vertices of G such that every vertex of G has at most k elements of X in its closed neighbourhood. The main aim in this paper is to prove the best-possible result that if G is a cubic graph, then L2(G) ≥ |V (G)|/3, improving the previous lower bound given by Gallant, et al. In addition, we construct an infinite family of graphs to show that lower bounds given by Gagarin and Zverovich are asymptotically best-possible, up to a constant factor, when k is fixed and Δ(G) tends to infinity. For Δ(G) tending to infinity and k tending to infinity sufficiently quickly, we give an asymptotically best-possible lower bound for Lk(G), improving previous bounds.