¿Cuál es la razón para llamar a los conjuntos independientes como conjuntos estables de un gráfico? ¿El conjunto estable dice algo más sobre el grafo que no sea un conjunto de vértices no adyacentes por pares?
Respuesta
¿Demasiados anuncios?
Misha
Puntos
1723
Los conjuntos "estables" solían llamarse conjuntos "internamente estables", y el número de independencia $\alpha(G)$ solía llamarse "coeficiente de estabilidad interna". Desgraciadamente, ninguno de los primeros que lo adoptaron explica por qué tiene sentido.
La primera aparición de los conjuntos "internamente estables" que pude encontrar fue en el artículo de Berge Dos teoremas de la teoría de grafos (1957), y más tarde en su libro de texto de 1958 sobre teoría de grafos. Es posible que en francés haya una conexión obvia entre la "estabilidad interna" y los vértices no adyacentes que justifique la terminología.
También puedo encontrar algunas referencias (por ejemplo este documento ) que se refieren a un conjunto dominante (es decir, un conjunto $S$ tal que cada vértice de $V(G) \setminus S$ tiene un vecino en $S$ ) como un conjunto "externamente estable".
