Article in volume
Authors:
Title:
Strengthening some complexity results on toughness of graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 401-419
Received: 2019-10-19 , Revised: 2020-10-10 , Accepted: 2020-10-13 , Available online: 2020-11-06 , https://doi.org/10.7151/dmgt.2372
Abstract:
Let $t$ be a positive real number. A graph is called $t$-tough if the removal
of any vertex set $S$ that disconnects the graph leaves at most $|S|/t$
components. The toughness of a graph is the largest $t$ for which the graph is
$t$-tough.
The main results of this paper are the following. For any positive rational
number $t \le 1$ and for any $k \ge 2$ and $r \ge 6$ integers recognizing
$t$-tough bipartite graphs is coNP-complete (the case $t=1$ was already known),
and this problem remains coNP-complete for $k$-connected bipartite graphs, and
so does the problem of recognizing 1-tough $r$-regular bipartite graphs. To
prove these statements we also deal with other related complexity problems on
toughness.
Keywords:
toughness, coNP-complete
References:
- D. Bauer, S.L. Hakimi and E. Schmeichel, Recognizing tough graphs is NP-hard, Discrete Appl. Math. 28 (1990) 191–195.
https://doi.org/10.1016/0166-218X(90)90001-S - D. Bauer, A. Morgana and E. Schmeichel, On the complexity of recognizing tough graphs, Discrete Math. 124 (1994) 13–17.
https://doi.org/10.1016/0012-365X(92)00047-U - D. Bauer, J. van den Heuvel, A. Morgana and E. Schmeichel, The complexity of recognizing tough cubic graphs, Discrete Appl. Math. 79 (1997) 35–44.
https://doi.org/10.1016/S0166-218X(97)00030-9 - D. Bauer, J. van den Heuvel, A. Morgana and E. Schmeichel, The complexity of toughness in regular graphs, Congr. Numer. 130 (1998) 47–61.
- D. Bauer, H.J. Broersma and H.J. Veldman, Not every $2$-tough graph is Hamiltonian, Discrete Appl. Math. 99 (2000) 317–321.
https://doi.org/10.1016/S0166-218X(99)00141-9 - V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228.
https://doi.org/10.1016/0012-365X(73)90138-6 - B. Jackson and P. Katerinis, A characterization of $3/2$-tough cubic graphs, Ars Combin. 38 (1994) 145–148.
- D. Kratsch, J. Lehel and H. Müller, Toughness, Hamiltonicity and split graphs, Discrete Math. 150 (1996) 231–245.
https://doi.org/10.1016/0012-365X(95)00190-8 - C.H. Papadimitriou and M. Yannakakis, The complexity of facets $($and some facets of complexity$)$, J. Comput. System Sci. 28 (1984) 244–259.
https://doi.org/10.1016/0022-0000(84)90068-0
Close