Date of Award
Spring 2022
Document Type
Open Access Dissertation
Department
Mathematics
First Advisor
Éva Czabarka
Second Advisor
László Székely
Abstract
This dissertation is split into three sections, each containing new results on a particular combinatorial problem. In the first section, we consider the set of 3-connected quadrangulations on n vertices and the set of 5-connected triangulations on n vertices. In each case, we find the minimum Wiener index of any graph in the given class, and identify graphs that obtain this minimum value. Moreover, we prove that these graphs are unique up to isomorphism.
In the second section, we work with structures emerging from the biological sciences called tanglegrams. In particular, our work pertains to an invariant of tanglegrams called the tangle crossing number, an invariant which is NP-hard to compute. Czabarka, Székely, and Wagner found a finite characterization of tanglegrams with tangle crossing number equal to 0, which motivated the work here. In particular, our aim was to find a similar finite (and minimal) characterization of tanglegrams with tangle crossing number at least k, for any fixed k ≥ 2. We set out to prove this using an elegant order-theoretic argument, but came to another surprising result instead; we proved that the set of tanglegrams with the induced subtanglegram relation is not a well partial order.
In the final section, we work on the problem of finding an upper bound on the diameter of graphs with particular properties. It was proven independently by several groups that for fixed minimum degree $\delta\ge 2$, every connected graph $G$ of order $n$ satisfies diam$(G)\le \dfrac{3n}{\delta + 1} + O(1)$ as $n\rightarrow \infty$. Erd\H{o}s, Pach, Pollack, and Tuza noticed that the graphs which achieve the aforementioned bound all contain complete subgraphs whose order increases with $n$, and conjectured that if we disallowed complete subgraphs of a given fixed size, then we could improve the bound. Czabarka, Singgih, and Sz\'ekely recently found a counterexample to part of the conjecture of Erd\H{o}s \emph{et al.} and formulated a new conjecture. Under a stronger assumption, we verify two cases of this new conjecture using a novel unified duality approach.
Rights
© 2022, Stephen Smith
Recommended Citation
Smith, S.(2022). Results on Select Combinatorial Problems With an Extremal Nature. (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/6836