University of TehranJournal of Algorithms and Computation2476-277651220191201Tenacious Graph is NP-hard12713475276ENDaraMoazzamiDepartment of Algorithms and Computation, Faculty of Engineering Science, College of Engineering, University of Tehran, Iran,Journal Article20200304The tenacity of a graph $G$, $T(G)$, is defined by<br />$T(G) = min{frac{mid Smid +tau(G-S)}{omega(G-S)}}$, where the<br />minimum is taken over all vertex cutsets $S$ of $G$. We define<br />$tau(G - S)$ to be the number of the vertices in the largest<br />component of the graph $G-S$, and $omega(G-S)$ be the number of<br />components of $G-S$. In this paper<br />we consider the relationship between the minimum degree $delta (G)$ of a graph and the complexity<br />of recognizing if a graph is $T$-tenacious. Let $Tgeq 1$ be a rational number. We first show that if<br />$delta(G)geq frac{Tn}{T+1}$, then $G$ is $T$-tenacious. On the other hand, for any fixed $epsilon>0$, we<br />show that it is $NP$-hard to determine if $G$ is $T$-tenacious, even for the class of graphs with $delta(G)geq<br />(frac{T}{T+1}-epsilon )n$.https://jac.ut.ac.ir/article_75276_859179202bd0083eec05d9bf12027118.pdf