Existe algo conhecido sobre a classe de gráficos com a propriedade de que todos os conjuntos independentes máximos têm a mesma cardinalidade e, portanto, são ISs máximos?
Por exemplo, pegue um conjunto de pontos no plano e considere o gráfico de interseções entre todos os segmentos entre pares de pontos no conjunto. (segmentos-> vértices, interseções-> arestas). Este gráfico terá a propriedade acima, pois todos os ISs máximos correspondem a triangulações do conjunto de pontos original. Existem outras categorias de gráficos conhecidas por terem essa propriedade? Esta propriedade pode ser facilmente testada?
graph-theory
co.combinatorics
László Kozma
fonte
fonte
Respostas:
Esses gráficos são chamados de gráficos bem cobertos . Aqui está um artigo recente sobre o assunto que lista várias referências úteis. Como Suresh mencionou, o problema de reconhecimento é co-NP-completo.
Observe que os conjuntos independentes de um gráfico formam um complexo simplicial abstrato. Complexos simplicais que surgem dessa maneira são chamados de "complexos de independência" ou "complexos de bandeira". Um complexo simplicial é considerado puro se todo simplex máximo tiver a mesma cardinalidade. Portanto, você pode encontrar alguns artigos relevantes pesquisando "complexo de independência pura" ou "complexo de bandeira pura".
fonte
A propriedade MAXIMAL = MAXIMUM para conjuntos independentes em gráficos e estruturas combinatórias mais gerais é importante. Será interessante entender gráficos onde esta propriedade se aplica a todos os subgráficos induzidos. Um caso abstrato geral em que temos MAXIMUM = MAXIMAL é quando existe uma estrutura matróide subjacente, mas existem muitos outros casos, como o caso dos gráficos planares máximos mencionados na pergunta. Aqui está um exemplo relacionado: considere n pontos no plano na posição convexa e deixe k ser um número inteiro. Considere gráficos cujos vértices são segmentos de linha entre esses pontos, onde dois vértices são adjacentes se os segmentos de linha não se cruzarem. Dress provou que, para este gráfico, MAXIMIM = MAXIMAL para conjuntos independentes.
fonte