2019/10/19 by Gyula Y Katona, Katona, Gyula Y, Kitti Varga +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1910.08752
arxiv created 2019/10/19 · arxiv updated 2019/10/22
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. % In this paper we prove the following. For any positive rational number t, deciding whether τ(G)=t is DP-complete and if t < 1, this problem remains DP-complete for bipartite graphs. For any integer k ≥ 2 and positive rational number t ≤ 1, recognizing t-tough k-connected bipartite graphs is coNP-complete. For any integer r ≥ 5, recognizing 1/2-tough r-regular graphs is coNP-complete. For any integer r ≥ 6, recognizing 1-tough r-regular bipartite graphs is coNP-complete. For any positive rational number t < 2/3 we give a polynomial time algorithm for recognizing 3-regular graphs with toughness t. Finally, we prove that every connected 4-regular graph is 1/2-tough.