The graph realization problem: obtaining a graph if we know the degrees of its vertices

What is it about?

Two cases to solve the realization problem can arise: • finding a graph which satisfies the conditions, • finding all graphs which satisfy the conditions. A sequence of non-negative integers is called graphical if it is the degree sequence of some graph. * Necessary and sufficient conditions for a sequence of integers to be graphical * Algorithms • Testing possible solutions • Determining a solution with binary integer programming algorithm • Testing the graphical sequence property based on Erdös–Gallai theorem • Graph realization problem using the Havel–Hakimi theorem • Graph realization problem using the Kleitman–Wang theorem • Graph realization problem using flow networks • A modified Edmonds–Karp algorithm for undirected graphs • Appendix: Determining the closed alternating semipaths

Featured Image

Why is it important?

Despite the fact that the graph realization problem has been intensively studied, there are still many new ideas. The necessary and sufficient conditions for the realization problem have been known for long, and from these it is easy to give algorithms, yet their exact description in pseudocode is not in vain, because it helps to investigate the complexity of these algorithms. We also examined the possibility of finding all solutions, excluding isomorphic graphs, and the possibility of a parallel approach for larger graph orders. The algorithm to solve the problem using network flows for directed graphs has been modified so that it can be applied to undirected graphs as well. In addition, we have presented an algorithm that solves the problem by integer linear programming.