{k}-packing functions of graphs

E. HINRICHSEN; V. LEONI

LECTURE NOTES IN COMPUTER SCIENCE

Springer

Año: 2014 vol. 8596 p. 325 - 335

0302-9743

Given a positive integer $k$ and a graph $G$,  a $k$-limited packing in $G$ (2010) is a subset $B$ of its vertex set such that each closed neighborhood has at most $k$ vertices of $B$. As a variation, we introduce the notion of a emph{${k}$-packing function} $f$ of $G$ which assigns a non-negative integer to the vertices of $G$ in such a way that the sum of $f(v)$ over each closedneighborhood is at most $k$.  For fiixed $k$, we prove that the problem of finding a ${k}$-packing function of maximum weight (${k$}PF) can be reduced linearly to the problem of finding a $k$-limited packing of maximum cardinality ($k$LP).  We present an $O(|V(G)|+|E(G)|)$ time algorithm to solve ${k$}PF on strongly chordal graphs. We also use monadic second-order logic to prove that both problems are linear time solvable for graphs with clique-width bounded by a constant.