complejo independencia

El complejo de independencia de un gráfico es un objeto matemático que describe los conjuntos independientes del gráfico. Formalmente, el complejo de independencia de un grafo no dirigido G , denotado por I( G ), es un complejo simplicial abstracto (es decir, una familia de conjuntos finitos cerrados bajo la operación de tomar subconjuntos), formado por los conjuntos de vértices en los independientes conjuntos de G. _ Cualquier subconjunto de un conjunto independiente es en sí mismo un conjunto independiente, por lo que I( G ) es cerrado al tomar subconjuntos.

Todo conjunto independiente en un grafo es un clique en su grafo complementario y viceversa. Por tanto, el complejo de independencia de un grafo es igual al complejo clique de su grafo complementario, y viceversa.

Varios autores estudiaron las relaciones entre las propiedades de un grafo G = ( V , E ), y los grupos de homología de su complejo de independencia I( G ). ^[1] En particular, varias propiedades relacionadas con los conjuntos dominantes en G garantizan que algunos grupos de homología reducida de I( G ) son triviales.

1. El número de dominación total de G, denotado , es la cardinalidad mínima de un conjunto dominante total de G - un conjunto S tal que cada vértice de V es adyacente a un vértice de S . Si entonces _ ^[2] ${\ estilo de visualización \ gamma _ {0} (G)}$ ${\ estilo de visualización \ gamma _ {0} (G)> k}$ ${\tilde {H}}_{k-1}(I(G))=0$

2. El número de dominación total de un subconjunto A de V en G, denotado , es la cardinalidad mínima de un conjunto S tal que cada vértice de A es adyacente a un vértice de S . El número de dominación independiente de G, denotado , es el máximo, sobre todos los conjuntos independientes A en G , de . Si , entonces . ^[1]^[3] ${\ estilo de visualización \ gamma _ {0} (G, A)}$ $i\gamma (G)$ ${\ estilo de visualización \ gamma _ {0} (G, A)}$ $i\gamma (G)>k$ ${\tilde {H}}_{k-1}(I(G))=0$