2018/12/22 by Escalante, Mariana, Hinrichsen, Erica, Leoni, Valeria.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1812.09422
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].