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

Abstract

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.