Spanning paths, cycles and trees: problems and results

Abstract

This thesis deals with the classical graph theoretic structures- spanning paths, cycles and trees. We here present new sufficient conditions for a graph to possess Hamiltonian (spanning) paths. New sufficient conditions for a graph to be Hamiltonian are also presented. We here basically deal with degree related conditions. Also, a new parameter, namely shortest path distance, is introduced in a sufficient condition we present. The infamous Ore's theorem is shown to follow from our results, which prove the significance of our conditions. Furthermore the relation between independence number of a graph and hamiltonicity is also explored in this thesis. Spanning trees have numerous applications in both practical and theoretical problems. We here present some new spanning tree problems and consider the issues of their complexity. The relation between independence number and a special spanning tree, namely degree bounded spanning tree is also explored. Finally, we introduce a new notion of "set version" of some decision problems having integer K < IVI as a parameter in the input instance, where we replace K by a set X ,;;; IVI. For example, the set version of maximum leaf spanning tree problem asks whether there exists a spanning tree in G that contains X as a subset of the leaf set. We raise the issue of whether the set versions of NP-Complete problems are as hard as the original problems and prove that although in some cases the set versions are easier to solve, this is not necessarily true in general.