Labelled packing functions in graphs

Resumen

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 $\lbrace k\rbrace$-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 $\lbrace k\rbrace$-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).

Publicación
Information Processing Letters 154 (2020), 105863