On Path-Tough Graphs
Peter Dankelmann, Thomas E.W Nießen, Ingo Schiermeyer · SIAM Journal on Discrete Mathematics · 1994
A graph G is called path-tough, if, for each nonempty set S of vertices, the graph $G - S$ can be covered by at most $|S|$ vertex disjoint paths. The authors prove that every graph of order n and minimum degree at least $[ 3/( 6 + \sqrt{3} ) ]n$ is Hamiltonian if and only if it is path-tough. Similar results involving the degree sum of two or three independent vertices, respectively, are given. Moreover, it is shown that every path-tough graph without three independent vertices of degree 2 contains a 2-factor. The authors also consider complexity aspects and prove that the decision problem of whether a given graph is path-tough is NP-complete.