Physical Sciences and Mathematics Commons^™

Tangled Up In Tanglegrams, Drew Joseph Scalzo

Theses and Dissertations

Tanglegrams are graphs consisting of two rooted binary plane trees with the same number of leaves and a perfect matching between the two leaf sets. A Tanglegram drawing is a special way of drawing a Tanglegram; and a Tanglegram is called planar if it has a drawing such that the matching edges do not cross. In this thesis, we will discuss various results related to the construction and planarity of Tanglegrams, as well as demonstrate how to construct all the Tanglegrams of size 4 by looking at two types of rooted binary trees - Caterpillar and Complete Binary Trees. After …

Results On Select Combinatorial Problems With An Extremal Nature, Stephen Smith

Theses and Dissertations

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 …

Some Extremal And Structural Problems In Graph Theory, Taylor Mitchell Short

Theses and Dissertations

This work considers three main topics. In Chapter 2, we deal with König-Egerváry graphs. We will give two new characterizations of König-Egerváry graphs as well as prove a related lower bound for the independence number of a graph. In Chapter 3, we study joint degree vectors (JDV). A problem arising from statistics is to determine the maximum number of non-zero elements of a JDV. We provide reasonable lower and upper bounds for this maximum number. Lastly, in Chapter 4 we study a problem in chemical graph theory. In particular, we characterize extremal cases for the number of maximal matchings in …

Spectral Analysis Of Randomly Generated Networks With Prescribed Degree Sequences, Clifford Davis Gaddy

Theses and Dissertations

Network science attempts to capture real-world phenomenon through mathematical models. The underlying model of a network relies on a mathematical structure called a graph. Having seen its early beginnings in the 1950's, the field has seen a surge of interest over the last two decades, attracting interest from a range of scientists including computer scientists, sociologists, biologists, physicists, and mathematicians. The field requires a delicate interplay between real-world modeling and theory, as it must develop accurate probabilistic models and then study these models from a mathematical perspective. In my thesis, we undertake a project involving computer programming in which we …

Properties Of The Zero Forcing Number, Kayla Denise Owens

Theses and Dissertations

The zero forcing number is a graph parameter first introduced as a tool for solving the minimum rank problem, which is: Given a simple, undirected graph G, and a field F, let S(F,G) denote the set of all symmetric matrices A=[a_{ij}] with entries in F such that a_{ij} doess not equal 0 if and only if ij is an edge in G. Find the minimum possible rank of a matrix in S(F,G). It is known that the zero forcing number Z(G) provides an upper bound for the maximum nullity of a graph. I investigate properties of the zero forcing number, …