| The main topics of this dissertation are extremal graph theory and algebraic graph theory. With Balister, Bollobas and Pebody, we studied a question of algebraic graph theory involving a relatively new graph invariant, namely the interlace polynomial. This polynomial is defined using a striking recurrence relation involving a fairly brutal graph operation. We were able to prove a conjecture of Arratia, Bollobas and Sorkin about the value of the interlace polynomial at -1. In a result related to extremal graph theory, we found the sequence of graphs where the modulus of the interlace polynomial at -1 is maximal.; The second part of this dissertation involves a study of the geodetic number of digraphs, which was introduced by Chartrand and Zhang. It is a graph parameter that measures, in some sense, the number of vertices along shortest paths between other vertices. With Pebody, we were able to prove several conjectures proposed by Chartrand and Zhang. While seemingly unrelated to extremal graph theory, one of our results gives a general upper bound on the lower geodetic number of an ordinary graph, and provides a sequence of graphs that show this bound is tight for all odd numbers of vertices.; Ramsey theory has a well known history involving contributions of Erdo&huml;s, Szekeres, Thomason and many others. Ramsey theory has traditionally concerned itself with the study of monochromatic subgraphs in a large graph. In work with Montagh, we were able to answer a question involving specifically colored subgraphs. We hope to follow up this result with many others along the same lines.; One major question of extremal graph theory involves studying the number of edges a graph may have if it contains no subgraph isomorphic to a specified smaller graph. The minimum degree of a graph is, in some sense, a measure of the number of edges in a graph. Thus, results like Dirac's theorem on the existence of a Hamiltonian cycle are extremal. Horak posed a conjecture about trees with bounded maximum degree through specified vertices of a minimum degree in the original graph. I was able to prove this conjecture. |
