1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Strengthening Some Complexity Results on Toughness of Graphs

Published Online: 24 Nov 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 19 Oct 2019
Accepted: 13 Oct 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 ≤ 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

MSC 2010

[1] D. Bauer, S.L. Hakimi and E. Schmeichel, Recognizing tough graphs is NP-hard, Discrete Appl. Math. 28 (1990) 191–195. doi:10.1016/0166-218X(90)90001-S10.1016/0166-218X(90)90001-SSearch in Google Scholar

[2] D. Bauer, A. Morgana and E. Schmeichel, On the complexity of recognizing tough graphs, Discrete Math. 124 (1994) 13–17. doi:10.1016/0012-365X(92)00047-U10.1016/0012-365X(92)00047-USearch in Google Scholar

[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. doi:10.1016/S0166-218X(97)00030-910.1016/S0166-218X(97)00030-9Search in Google Scholar

[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.Search in Google Scholar

[5] D. Bauer, H.J. Broersma and H.J. Veldman, Not every 2-tough graph is Hamiltonian, Discrete Appl. Math. 99 (2000) 317–321. doi:10.1016/S0166-218X(99)00141-910.1016/S0166-218X(99)00141-9Search in Google Scholar

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

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

[8] D. Kratsch, J. Lehel and H. Müller, Toughness, Hamiltonicity and split graphs, Discrete Math. 150 (1996) 231–245. doi:10.1016/0012-365X(95)00190-810.1016/0012-365X(95)00190-8Search in Google Scholar

[9] C.H. Papadimitriou and M. Yannakakis, The complexity of facets (and some facets of complexity), J. Comput. System Sci. 28 (1984) 244–259. doi:10.1016/0022-0000(84)90068-010.1016/0022-0000(84)90068-0Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo