Extremal properties of degree sequences: potential functions for subgraphs and forbidden subgraphs
Loading...
Date
2022-08-04
Authors
Penner, Alex
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Any pair of graphs with the same degree sequence have the same number of edges, but they may not have the same subgraphs. In 1991 Erdős, Jacobson, and Lehel, introduced the concept of the `potential function' of a graph H: the least number of edges in a graph on n vertices for which some other graph with the same degree sequence contains a copy of a fixed graph H. They gave a conjecture for the value of the potential function for the case when H is complete that has since been shown to be true when n is sufficiently large in terms of the order of H. This thesis gives a survey of these results and the techniques used to prove them. For arbitrary graphs H, this thesis also provides asymptotic results about the potential function along with some properties of sequences without such realizations. Finally, I present some original results about the maximum number of edges in a graph whose degree sequence has realizations avoiding H. To avoid some trivial cases, the problem is restricted to connected realizations and is solved completely in the cases that either H is complete or a small cycle. I then present a conjecture for all larger cycles along with supporting results.
Description
Keywords
extremal graph theory, degree sequence, potential function