Graph realization problem

The graph realization problem is a decision problem in graph theory. Given a finite sequence of natural numbers, the problem asks whether there is labeled simple graph such that is the degree sequence of this graph.

Solutions

The problem can be solved in polynomial time. One method of showing this uses the Havel–Hakimi algorithm constructing a special solution with the use of a recursive algorithm.[1][2] Alternatively, following the characterization given by the Erdős–Gallai theorem, the problem can be solved by testing the validity of inequalities.[3]

Other notations

The problem can also be stated in terms of symmetric matrices of zeros and ones. The connection can be seen if one realizes that each graph has an adjacency matrix where the column sums and row sums correspond to . The problem is then sometimes denoted by symmetric 0-1-matrices for given row sums.

Similar problems describe the degree sequences of simple bipartite graphs or the degree sequences of simple directed graphs. The first problem is the so-called bipartite realization problem. The second is known as the digraph realization problem.

The problem of constructing a solution for the graph realization problem with the additional constraint that each such solution comes with the same probability was shown to have a polynomial-time approximation scheme for the degree sequences of regular graphs by Cooper, Martin, and Greenhill.[4] The general problem is still unsolved.

gollark: That sounds like one of those things where they test a ridiculous amount of ways to extract information/random noise from the Bible and, amazingly, find that sometimes random noise seems like an interesting thing.
gollark: They weren't very *good* steam engines; they were missing steel or something.
gollark: No, I mean what do they interact with and what's the evidence of it.
gollark: > without a creation there is no world staying aliveAgain, please actually explain this?
gollark: But it would be nice if you would explain how this god interferes to keep the world from imploding or something.

References
  1. Havel, Václav (1955), "A remark on the existence of finite graphs", Časopis Pro Pěstování Matematiky (in Czech), 80: 477–480.
  2. Hakimi, S. L. (1962), "On realizability of a set of integers as degrees of the vertices of a linear graph. I", Journal of the Society for Industrial and Applied Mathematics, 10 (3): 496–506, doi:10.1137/0110037, hdl:10338.dmlcz/128153, MR 0148049.
  3. Erdős, P.; Gallai, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF), Matematikai Lapok, 11: 264–274.
  4. Cooper, Colin; Dyer, Martin; Greenhill, Catherine (2007), "Sampling regular graphs and a peer-to-peer network", Combinatorics, Probability and Computing, 16 (4): 557–593, CiteSeerX 10.1.1.181.597, doi:10.1017/S0963548306007978, MR 2334585.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.