@article {
author = {Moazzami, Dara},
title = {Tenacious Graph is NP-hard},
journal = {Journal of Algorithms and Computation},
volume = {51},
number = {2},
pages = {127-134},
year = {2019},
publisher = {University of Tehran},
issn = {2476-2776},
eissn = {2476-2784},
doi = {10.22059/jac.2019.75276},
abstract = {The tenacity of a graph $G$, $T(G)$, is defined by$T(G) = min\{\frac{\mid S\mid +\tau(G-S)}{\omega(G-S)}\}$, where theminimum is taken over all vertex cutsets $S$ of $G$. We define$\tau(G - S)$ to be the number of the vertices in the largestcomponent of the graph $G-S$, and $\omega(G-S)$ be the number ofcomponents of $G-S$. In this paperwe consider the relationship between the minimum degree $\delta (G)$ of a graph and the complexityof recognizing if a graph is $T$-tenacious. Let $T\geq 1$ be a rational number. We first show that if$\delta(G)\geq \frac{Tn}{T+1}$, then $G$ is $T$-tenacious. On the other hand, for any fixed $\epsilon>0$, weshow that it is $NP$-hard to determine if $G$ is $T$-tenacious, even for the class of graphs with $\delta(G)\geq(\frac{T}{T+1}-\epsilon )n$.},
keywords = {minimum degree,Complexity,Tenacity,$NP$-hard,$T$-tenacious},
url = {https://jac.ut.ac.ir/article_75276.html},
eprint = {https://jac.ut.ac.ir/article_75276_859179202bd0083eec05d9bf12027118.pdf}
}