Article ID Journal Published Year Pages File Type
4648077 Discrete Mathematics 2012 7 Pages PDF
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).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,