Polynomial algorithms that prove an NPhard hypothesis implies an NPhard conclusion
Bauer, D. and Broersma, H.J. and Morgana, A. and Schmeichel, E. (1999) Polynomial algorithms that prove an NPhard hypothesis implies an NPhard conclusion. [Report]
 PDF 161Kb 
Abstract:  A number of results in Hamiltonian graph theory are of the form implies , where is a property of graphs that is NPhard and is a cycle structure property of graphs that is also NPhard. Such a theorem is the wellknown ChvtalErds Theorem, which states that every graph with is Hamiltonian. Here is the vertex connectivity of and is the cardinality of a largest set of independent vertices of . In another paper Chvtal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than independent vertices. In this note we point out that other theorems in Hamiltonian graph theory have a similar character. In particular, we present a constructive proof of the wellknown theorem of Jung for graphs on or more vertices..

Item Type:  Report 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/65687 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 141297