#### Date of Award

2016

#### Document Type

Open Access Dissertation

#### Department

Mathematics

#### Sub-Department

College of Arts and Sciences

#### First Advisor

László Székely

#### Abstract

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 two linear polymers of chemical interest: the polyspiro chains and benzenoid chains. We also enumerate maximal matchings in several classes of these linear polymers and use the obtained results to determine the asymptotic behavior of these matchings.

#### Recommended Citation

Short, T. M.(2016). *Some Extremal And Structural Problems In Graph Theory.* (Doctoral dissertation). Retrieved from http://scholarcommons.sc.edu/etd/3753