ON PATH-TOUGH GRAPHS

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 + root 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.