Extremal properties of degree sequences: potential functions for subgraphs and forbidden subgraphs
| dc.contributor.author | Penner, Alex | |
| dc.contributor.examiningcommittee | Kamali, Shahin (Computer Science) | en_US |
| dc.contributor.examiningcommittee | Prymak, Andriy (Mathematics) | en_US |
| dc.contributor.supervisor | Gunderson, Karen | |
| dc.date.accessioned | 2022-08-05T13:45:02Z | |
| dc.date.available | 2022-08-05T13:45:02Z | |
| dc.date.copyright | 2022-08-04 | |
| dc.date.issued | 2022-08-04 | |
| dc.date.submitted | 2022-08-04T22:27:12Z | en_US |
| dc.degree.discipline | Mathematics | en_US |
| dc.degree.level | Master of Science (M.Sc.) | en_US |
| dc.description.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. | en_US |
| dc.description.note | October 2022 | en_US |
| dc.identifier.uri | http://hdl.handle.net/1993/36665 | |
| dc.language.iso | eng | en_US |
| dc.rights | open access | en_US |
| dc.subject | extremal graph theory | en_US |
| dc.subject | degree sequence | en_US |
| dc.subject | potential function | en_US |
| dc.title | Extremal properties of degree sequences: potential functions for subgraphs and forbidden subgraphs | en_US |
| dc.type | master thesis | en_US |
| local.subject.manitoba | no | en_US |
| oaire.awardTitle | University of Manitoba Graduate Fellowship | en_US |
| oaire.awardURI | https://umanitoba.ca/graduate-studies/funding-awards-and-financial-aid/university-manitoba-graduate-fellowship-umgf | en_US |
| project.funder.identifier | https://doi.org/10.13039/100010318 | en_US |
| project.funder.name | University Of Manitoba | en_US |