Packing functions and graphs with perfect closed neighbourhood matrices

arXiv1812.09422MaRDI QIDQ6311536FDOQ6311536

Authors: Mariana S. Escalante, E. Hinrichsen, V. Leoni 

Publication date: 21 December 2018

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 $kgeq2$ 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]$.

This page was built for publication: Packing functions and graphs with perfect closed neighbourhood matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6311536)