SOBRE LA RELACIÓN ENTRE LOS GRAFOS SOLES Y AQUELLOS CON MATRIZ DE VECINDAD CERRADA PERFECTA

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

Congreso; VirtUMA 2020; 2020

Unión Matemática Argentina

Previamente iniciamos con el estudio de propiedades de los grafos cuyamatriz de vecindades cerradas es perfecta y llamamos F a esta familia degrafos. M´as precisamente, para un grafo G con n = jV (G)j y denotando conN[G] a su matriz de vecindades cerradas, decimos que G 2 F si el poliedrofx 2 [0; 1]n : N[G]x ≤ 1g es un poliedro entero, donde 1 es el vector cuyascomponentes son todas iguales a 1.Dada la caracterizaci´on de Chv´atal de matrices perfectas como aquellas queson matrices clique-nodo de un grafo perfecto [2], en ese trabajo mostramos enprimer lugar una condici´on necesaria y suficiente sobre un grafo dado G paraque N[G] sea una matriz clique-nodo. Definimos otro grafo (asociado a G) quedenotamos como QG, como aquel con tantos nodos como G y tal que dos nodosest´an conectados en QG si existe una fila de N[G] con dos 1?s en las columnascorrespondientes a ellos. Debido al Teorema de Grafos Perfectos [1] sabemosque un grafo es perfecto si y solamente si no posee un agujero impar ni a sucomplemento como subgrafos inducidos por nodos. A partir de esta propiedad,hemos mostrado una caracterizaci´on para aquellos grafos G tales que QG noposee agujeros impares como subgrafos inducidos por nodos.En el presente trabajo avanzamos en dos sentidos en el estudio de la familiaF. Por un lado, estudiamos la relaci´on de contenci´on existente con algunasfamilias conocidas de grafos definidas a trav´es de ciertas propiedades de sumatriz de vecindades cerradas. En este sentido vimos la relaci´on de F con losgrafos fuertemente cordales, con los dualmente cordales, con los cordales, y por´ultimo con aquellos libres de soles.Luego, en relaci´on con estos ´ultimos resultados y los de Brouwer et al. en [3],estudiamos la familia de los grafos soles y una extensi´on de ellos a los grafos nocordales. Probamos que la estructura presente en G para que el grafo QG tengaun agujero impar inducido (y entonces no pertenezca a F) est´a fuertementerelacionada con los grafos soles impares. Finalmente, a partir de este ´ultimoresultado pudimos identificar qu´e grafos soles y extensiones a grafos soles nocordales pertenecen a F.Nos proponemos continuar con el estudio de la relaci´on de F con otrasfamilias conocidas de grafos para completar as´ı una descripci´on completa de losgrafos que pertenecen a ella.References[1] Chudnovsky M., Robertson N., Seymour P., Thomas R., The strong perfectgraph theorem, Annals of Mathematics, 164 (2006), 51-229.[2] Chv´atal, V., On Certain Polytopes Associated with Graphs, Journal of Combinatorial Theory (B) 18 (1975), 138{154. 1991) 166-190.[3] Brouwer A. Duchet P., Schrijver A., Graphs whose neighborhood have nospecial cycles, Discrete Mathematics 47 (1983), 177-182.