View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Graphical realizations of degree sequences, packing multiple colors and random graphs

        Thumbnail
        View/Open
        Thesis.pdf (843.1Kb)
        Publication date
        2023
        Author
        Vries, Mike de
        Metadata
        Show full item record
        Summary
        Given a graph, one obtains its degree sequence by placing the degrees of the vertices in an ordered list. We are interested in the reverse problem: How do you go from a list of arbitrary natural numbers to a graphical realization with that list as its degree sequence? In 1960, Paul Erdős and Tibor Gallai solved the existence problem. By verifying a list of inequalities, one can determine whether a graphical realization exists. We continue the research on this question by first determining which lists have a unique graphical realization. We then investigate the problem of ‘packing’ multiple lists, that is verifying if there are edge-disjoint graphical realizations for each list. Although this problem is NP hard in general, we give some sufficient conditions. We also show that this problem can be solved in polynomial time for a specific case, when one packs a list of degrees with a given fixed graph. Finally, we investigate the problem of randomly generating graphical realizations. In 2010, a paper published by Mohsen Bayati, Jeong Han Kim and Amin Saberi gave a sequential algorithm. If the degrees are asymptotically not too large, then choosing the right bias on the edges results in an asymptotically uniform distribution of graphical realizations. This same approach has been applied to directed graphs and coloured graphs. We generalise these related results by bringing them under one framework for generating random maximum independent sets in a certain meta-graph.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/43718
        Collections
        • Theses
        Utrecht university logo