Search

In this thesis, we investigate a number of problems related to spanning substructures of graphs. The first few chapters consider extremal problems related to the number of forest-like structures of a graph. We prove that one can find a threshold graph which contains the minimum number of spanning pseudoforests, as well as rooted spanning forests, amongst all graphs on n vertices and e edges. This has left the open question of exactly which threshold graphs have the minimum number of these spanning substructures. We make progress towards this question in particular cases of spanning pseudoforests. The final chapter takes on a different flavor—we determine the complexity of a problem related to Hamilton cycles in hypergraphs. Dirac's theorem states that graphs with minimum degree at least half the size of the vertex set are guaranteed to have a Hamilton cycle. In 1993, Karpinksi, Dahlhaus, and Hajnal proved that for any c < ½, the problem of determining whether a graph with minimum degree at least cn has a Hamilton cycle is NP-complete. The analogous problem in hypergraphs, for both a Dirac-type condition and complexity, are just as interesting. We prove that for classes of hypergraphs with certain minimum vertex degree conditions, the problem of determining whether or not they contain an l-Hamilton cycle is NP-complete.