Packing functions and graphs with perfect closed neighbourhood matrices
share
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 ≥ 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].
READ FULL TEXT