SOME PROPERTIES OF {k}-PACKING FUNCTION PROBLEM IN GRAPHS

Abstract

The recently introduced {k}-packing function problem is considered in this paper. Relationship between cases when k = 1, k ≥ 2 and linear programming relaxation are introduced with sufficient conditions for optimality. For arbitrary simple connected graph G, we propose a construction procedure for finding values of k for which L{k}(G) can be determined in the polynomial time. Additionally, relationship between {1}-packing function and independent set number is established. Optimal values for some special classes of graphs and general upper and lower bounds are introduced, as well.