On the Complexity of Recognizing Tenacious Graphs

Abstract

We consider the relationship between the minimum degree $\delta (G$ of a graph and the complexity of recognizing if a graph is $T$-tenacious. Let $T\ge 1$ be a rational number. We first show that if $\delta (G)\ge \frac{Tn}{T+1}$ then $G$ is $T$-tenacious. On the other hand, for any fixed $ϵ>0$, we show that it is NP-hard to determine if $G$ is $T$-tenacious, even for the class of graphs with $\delta (G)\ge (\frac{T}{T+1}–ϵ)n$.