Packing functions and graphs with perfect closed neighbourhood matrices

Abstract

In this work we consider a straightforward linear programming formulation of the recently introduced $\{k\}$-packing function problem in graphs, for each fixed value of the positive integer number $k$. We analyse a special relation between the case $k=1$ and $k\ge 2$ and give a sufficient condition for optimality ---the perfection--- of the closed neighbourhood matrix $N[G]$ of the input graph $G$. We begin a structural study of graphs satisfying this condition. In particular, we look for a characterization of graphs that have perfect closed neighbourhood matrices which involves the property of being a clique-node matrix of a perfect graph. We present a necessary and sufficient condition for a graph to have a clique-node closed neighbourhood matrix. Finally, we study the perfection of the graph of maximal cliques associated to $N[G]$.

14 pages, 4 figures