Sobre la conjetura de los rangos N0-N sobre familias particulares de grafos near perfect

AGUILERA, NESTOR EDGARDO; ESCALANTE, MARIANA SILVINA; FEKETE, PABLO GABRIEL

Cordoba

Congreso; IV Congreso latinoamericano de Matemáticos; 2012

CLAM

Estudiamos los operadores N0 y N [2, 3, 1] en el contexto del problema del maximo conjunto estable en un grafo. Partiendo de la relajacion por arcos, las sucesivas iteraciones de N0 y N (indicadas con Nk_0 (G) y Nk(G)) convergen en a lo sumo |V| pasos a STAB(G), capsula convexa de los vectores caractersticos de los conjuntos estables en el grafo G. Esto motiva el estudio del rango N de G, r(G) = min{k : Nk(G) = STAB(G)}, y su analogo, r0(G) para el operador N0. Si bien, en general, Nk(G) ( Nk_0 (G) para k > 1, no se conocen ejemplos donde r(G) distinto r0(G). Es mas, en [3] se establecio la conjetura de que estos rangos coinciden para todo grafo G, la cual es valida sobre los grafos bipartitos, los serie-paralelos y los grafos perfectos, entre otros [1]. Estudiamos una familia de grafos que generaliza a la de los grafos perfectos, llamados near-perfect [4], donde STAB(G) esta descripto por las desigualdades de clique y solo una desigualdad mas: la desigualdad de rango del grafo. En este trabajo vericamos la validez de la conjetura de los rangos sobre subfamilias de grafos near-perfect.