Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648077 | Discrete Mathematics | 2012 | 7 Pages |
Abstract
By a 2-packing in a graph we mean a subset of its vertex set, in which all the vertices are in distance at least 3 from each other.The question about the maximum number of 2-packings in a graph is strongly related to the problem of L(2,1)L(2,1)-labeling of graphs.In this paper we find new asymptotic upper and lower bounds on the maximum number of 2-packings in a connected graph on nn vertices. The bounds are O(1.5399…n)O(1.5399…n) and Ω(1.4970…n)Ω(1.4970…n), respectively.Moreover, we present a lower bound on the number of kk-element 2-packings in a connected graph, which is max(n−2k+2k,(k+1)⌊n−12⌋k).
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Konstanty Junosza-Szaniawski, Paweł Rzążewski,