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.
