On path-tough graphs


P. Dankelmann, T. Niessen, I. Schiermeyer,


        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.

BibTEX Reference Entry 

	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,


 Download bibtex-file

Sorry, this paper is currently not available for download.