• Libraries
    • Log in to:
    View Item 
    •   MSpace Home
    • Faculty of Graduate Studies (Electronic Theses and Practica)
    • FGS - Electronic Theses and Practica
    • View Item
    •   MSpace Home
    • Faculty of Graduate Studies (Electronic Theses and Practica)
    • FGS - Electronic Theses and Practica
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Extremal properties of degree sequences: potential functions for subgraphs and forbidden subgraphs

    Thumbnail
    View/Open
    Thesis (812.3Kb)
    Date
    2022-08-04
    Author
    Penner, Alex
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1993/36665
    Collections
    • FGS - Electronic Theses and Practica [25515]

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of MSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Login

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV