Sobre el rango disyuntivo de grafos web

BIANCHI, SILVIA MARIA; ESCALANTE, MARIANA SILVINA; MONTELAR, MARÍA SUSANA

Cordoba

Congreso; IV Congreso latinoamericano de Matemáticos; 2012

CLAM

Consideramos el operador disyuntivo denido por Balas, Ceria y Cornuejols en [1] sobre la relajaciÓn clique del problema del mÁximo conjunto estable en grafos web. Es sabido que el rango disyuntivo de un grafo es el menor numero de nodos que se deben borrar de manera que el grafo resultante sea perfecto [2]. Esto permite encontrar una cota superior para el rango disyuntivo de cualquier grafo web. En este trabajo obtenemos el rango disyuntivo de cualquier grafo web Wk n y demostramos que la cota superior, k, es alcanzada, excepto por los grafos de la forma W^k_{3k+r} para r = 0 y r = 1, en los cuales el rango disyuntivo es k-2 y k-1, respectivamente. Nuestros resultados permiten estimar cotas para el rango disyuntivo de clases mas generales de grafos como los quasi-line y, sus complementos, los grafos near-bipartitos.