El efecto en k(G) de eliminar un vértice o una arista

Question

Consideremos un grafo (a, b) G (es decir, un grafo con a vértices y b aristas). Sea k (G), la cantidad mínima de vértices que pueden eliminarse para desconectar el grafo, n>=1.

¿Cuáles serían los posibles efectos sobre k(G) de eliminar un vértice o una arista de G?

Sé que k(G)<=delta(G) (el grado mínimo de todos los vértices de G), pero ¿es esto relevante? Eliminar una arista o un vértice reducirá delta(G) en uno si es incidente con el vértice de grado mínimo, pero esto sólo es relevante si k(G)=delta(G) y no dicta cuánto reduciría k(G).

Answer 1

La eliminación de un vértice puede reducir la conectividad en uno o dejarla sin cambios. La forma más fácil de demostrarlo es dar ejemplos como los que ha dado Leen. Es de esperar que la definición de conectividad deje claro que no se puede reducir más que eso.

Pero también podría aumentar la conectividad:

Considere $K_{n+1}$ con un vértice adicional $v$ pegado, adyacente a exactamente un vértice $w$ de la $K_{n+1}$ . Actualmente la conectividad es $1$ desde la eliminación de $w$ desconecta el gráfico, pero si eliminamos $v$ entonces nos queda $K_{n+1}$ que tiene conectividad $n$ .

Como ampliación podríamos conectar $v$ a $k<n$ vértices. Entonces $G$ es $k$ -conectado pero $G-v$ es $n$ -conectado.

Así que $\kappa(G-v)$ puede ser lo que queramos siempre que sea al menos $\kappa(G)-1$ .