En teoría de grafos , la tenacidad es una medida de la conectividad de un grafo. Se dice que un grafo G es t -tenaz para un número real dado t si, para cada entero k > 1 , G no se puede dividir en k componentes conexos diferentes mediante la eliminación de menos de tk vértices. Por ejemplo, un grafo es 1 -tenaz si el número de componentes formados al eliminar un conjunto de vértices es siempre, como máximo, tan grande como el número de vértices eliminados. La tenacidad de un grafo es el t máximo para el cual es t -tenaz; este es un número finito para todos los grafos finitos excepto los grafos completos , que por convención tienen tenacidad infinita.
La tenacidad de grafos fue introducida por primera vez por Václav Chvátal (1973). Desde entonces, otros matemáticos han realizado un amplio trabajo sobre la tenacidad; la encuesta reciente de Bauer, Broersma y Schmeichel (2006) enumera 99 teoremas y 162 artículos sobre el tema.
Quitar k vértices de un grafo de ruta puede dividir el grafo restante en hasta k + 1 componentes conectados. La proporción máxima de componentes a vértices eliminados se logra eliminando un vértice (del interior de la ruta) y dividiéndolo en dos componentes. Por lo tanto, las rutas son1/2 -duro. Por el contrario, eliminar k vértices de un gráfico de ciclo deja como máximo k componentes conectados restantes, y a veces deja exactamente k componentes conectados, por lo que un ciclo es 1 -duro.
Si un grafo es t -duro, entonces una consecuencia (que se obtiene al establecer k = 2 ) es que cualquier conjunto de 2 t − 1 nodos se puede eliminar sin dividir el grafo en dos. Es decir, cada grafo t -duro también es 2 t -conexo por vértices .
Chvátal (1973) observó que cada ciclo , y por lo tanto cada grafo hamiltoniano , es 1 -duro; es decir, ser 1 -duro es una condición necesaria para que un grafo sea hamiltoniano. Conjeturó que la conexión entre dureza y hamiltonicidad va en ambas direcciones: que existe un umbral t tal que cada grafo t -duro es hamiltoniano. La conjetura original de Chvátal de que t = 2 habría demostrado el teorema de Fleischner , pero fue refutada por Bauer, Broersma y Veldman (2000). La existencia de un umbral de dureza mayor para la hamiltonicidad sigue abierta, y a veces se denomina conjetura de dureza de Chvátal .
Comprobar si un grafo es 1 -duro es co-NP -completo. Es decir, el problema de decisión cuya respuesta es "sí" para un grafo que no es 1-duro, y "no" para un grafo que es 1-duro, es NP-completo . Lo mismo es cierto para cualquier número racional positivo fijo q : comprobar si un grafo es q -duro es co-NP-completo (Bauer, Hakimi y Schmeichel 1990).
