# On path-tough graphs

## Authors

## Abstract

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. We prove that every graph of order n and minimum degree at least n*3/(6+sqrt(3)) 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. We also consider complexity aspects and prove that the decision problem, whether a given graph is path-tough, is NP-complete.

## BibT_{E}X Reference Entry

@article{DaNiSc94, author = {Peter Dankelmann and Thomas Niessen and Ingo Schiermeyer}, title = "On path-tough graphs", pages = "571-584", journal = "SIAM J. Discrete Math.", volume = "7", year = 1994, }