Tenacious Graph is NP-hard
The tenacity of a graph $G$, $T(G)$, is defined by$T(G) = min{frac{mid Smid +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 $Tgeq 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$.the formula is not displayed correctly!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.