Geodesic
Strengthening some complexity results on toughness of graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 401-419 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 ≤ 1 and for any k ≥ 2 and r ≥ 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 
@article{DMGT_2023_43_2_a5,
     author = {Katona, Gyula Y. and Varga, Kitti},
     title = {Strengthening some complexity results on toughness of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {401--419},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a5/}
}
TY  - JOUR
AU  - Katona, Gyula Y.
AU  - Varga, Kitti
TI  - Strengthening some complexity results on toughness of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 401
EP  - 419
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a5/
LA  - en
ID  - DMGT_2023_43_2_a5
ER  - 
%0 Journal Article
%A Katona, Gyula Y.
%A Varga, Kitti
%T Strengthening some complexity results on toughness of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 401-419
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a5/
%G en
%F DMGT_2023_43_2_a5
Katona, Gyula Y.; Varga, Kitti. Strengthening some complexity results on toughness of graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 401-419. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a5/

[1] 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

[2] 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

[3] 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

[4] D. Bauer, J. van den Heuvel, A. Morgana and E. Schmeichel, The complexity of toughness in regular graphs, Congr. Numer. 130 (1998) 47–61.

[5] 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

[6] V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228. https://doi.org/10.1016/0012-365X(73)90138-6

[7] B. Jackson and P. Katerinis, A characterization of 3/2-tough cubic graphs, Ars Combin. 38 (1994) 145–148.

[8] 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

[9] 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