Sobre grafos con matrices de vecindades cerradas perfectas

ESCALANTE, MARIANA SILVINA; HINRICHSEN, ERICA; LEONI, VALERIA ALEJANDRA

Mendoza

Congreso; LXVIII Reunión Anual de Comunicaciones Científicas UMA y SOMACHI; 2019

UMA-SOMACHI

{En este trabajo estudiamos la familia F de los grafos G con matriz de vecindades cerradas, N[G], perfecta, i.e. {x∈[0,1]n:N[G]x≤1} es un poliedro entero, donde n=|V(G)| y 1 es el vector cuyas componentes son todas iguales a 1.}{Presentamos una caracterización parcial de la familia F a través de subgrafos inducidos prohibidos. }{A partir de la caracterización de matrices perfectas debida a Chvátal [2], es necesario probar que N[G] satisface dos propiedades, éstas son, ser matriz clique-nodo de un cierto grafo (denotado por QG) y la perfección del mismo.}{En primer lugar, identificamos a la familia de grafos cuya matriz de vecindades cerradas es clique-nodo, a través de la ausencia de un número finito de grafos de hasta siete nodos como subgrafos inducidos.}{Por [1], un grafo es perfecto si y solamente si no posee un agujero impar ni su complemento como subgrafo inducido por nodos. A partir de esta propiedad, en segundo lugar caracterizamos a aquellos grafos G tales que QG no posee agujeros impares como subgrafos inducidos por nodos. }{Las dos caracterizaciones halladas nos permiten derivar una descripción de una superfamilia de F a través de subgrafos inducidos prohibidos. }{La motivación original de este trabajo fue la de ampliar el conjunto de las instancias en las cuales el problema de optimización de la función {k}-empaquetadora en grafos puede ser resuelto en tiempo polinomial en función del tamaño de la entrada, conjunto al que pertenecen los grafos fuertemente cordales, entre otros [3, 4, 5].}{Referencias}{[1] Chudnovsky, M., G. Cornuéjols, X.Liu, P.Seymour and K.Vu\v sković, Recognizing Berge Graphs, Combinatorica 25 (2005), 143--187.}{[2] Chvátal, V., On Certain Polytopes Associated with Graphs, Journal of Combinatorial Theory (B) 18 (1975), 138--154. 1991) 166--190.}{[3] Conforti, M. and G. Cornuéjols, Balanced 0,+1,−1 Matrices, Bicoloring and Total Dual Integrality, Mathematical Programming 71 (1995), 249--258.}{[4] Farber, M., Characterizations of Strongly Chordal Graph, Discrete Mathematics 43 (1983), 173--189.}{[5] Hinrichsen, E. and V. Leoni, {k}-packing functions of graphs. Lecture Notes in Computer Science (2014), 325--335.}