Labelled packing functions in graphs

HINRICHSEN, ERICA G.; LEONI, VALERIA A.; SAFE, MARTÍN D.

INFORMATION PROCESSING LETTERS

ELSEVIER SCIENCE BV

Año: 2020 vol. 154

0020-0190

Given a positive integer k and a graph G, a k-limited packing in G is a subset B of its vertex set such that each closed vertex neighborhood of G has at most k vertices of B (Gallant et al., 2010). A first generalization of this concept deals with a subset of vertices that cannot be in the set B and also, the number k is not a constant but it depends on the vertex neighborhood (Dobson et al., 2010). As another variation, a {k}-packing function f of G assigns a non-negative integer to the vertices of G in such a way that the sum of the values of f over each closed vertex neighborhood is at most k (Hinrichsen et al., 2014). The three associated decision problems are NP-complete in the general case. We introduce L-packing functions as a unified notion that generalizes all limited packing concepts introduced up to now. We present a linear time algorithm that solves the problem of finding the maximum weight of an L-packing function in strongly chordal graphs when a strong elimination ordering is given that includes the linear algorithm for {k}-packing functions in strongly chordal graphs (2014). Besides, we show how the algorithm can be used to solve the known clique-independence problem on strongly chordal graphs in linear time (G. Chang et al., 1993).