ON PATH-TOUGH GRAPHS

A graph G is called path-tough, if, for each nonempty set S of vertice s, 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 l east [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 pa th-tough graph without three independent vertices of degree 2 contains a 2-factor. The authors also consider complexity aspects and prove th at the decision problem of whether a given graph is path-tough is NP-c omplete.