Vértices simpliciales y escalonabilidad de grafos

Abstract

RESUMEN: Dado un grafo simple no dirigido G, se le asocia un complejo simplicial ∆G cuyas caras corresponden a los conjuntos independientes de G. Van Tuyl y Villarreal definieron un grafo G como escalonable si el complejo simplicial asociado ∆G es escalonable en el sentido no puro de Bj¨orner y Wachs. Estos autores demostraron que todos los grafos triangulados son escalonables y que los grafos bipartidos escalonables son precisamente los grafos bipartidos secuencialmente Cohen-Macaulay. En el presente artÍculo se prueba que el concepto de vértice simplicial de un grafo permite, no solo demostrar estos resultados, sino dar otras condiciones necesarias y suficientes para la escalonabilidad de un grafo. Adem´as se demuestra que todo grafo simplicial es escalonable y que todo grafo arcocircular que contenga al menos un vértice simplicial es escalonable