Geodesic
Strengthening some complexity results on toughness of graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 401-419

Voir la notice de l'article provenant de la source Library of Science

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},
     publisher = {mathdoc},
     volume = {43},
     number = {2},
     year = {2023},
     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
PB  - mathdoc
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
%I mathdoc
%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/