Tenacious Graph is NP-hard

	Tenacious Graph is NP-hard
Journal of Algorithms and Computation
مقاله 11، دوره 51، شماره 2، اسفند 2019، صفحه 127-134 اصل مقاله (239.11 K)
شناسه دیجیتال (DOI): 10.22059/jac.2019.75276
نویسنده
Dara Moazzami^*
Department of Algorithms and Computation, Faculty of Engineering Science, College of Engineering, University of Tehran, Iran,
چکیده
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 the minimum is taken over all vertex cutsets $S$ of $G$. We define $\tau(G - S)$ to be the number of the vertices in the largest component of the graph $G-S$, and $\omega(G-S)$ be the number of components of $G-S$. In this paper 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\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$, we show 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$.
کلیدواژه‌ها
minimum degree؛ complexity؛ tenacity؛ $NP$-hard؛ $T$-tenacious

آمار تعداد مشاهده مقاله: 152 تعداد دریافت فایل اصل مقاله: 166

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب