Graph realization problem
The graph realization problem is a decision problem in graph theory.
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The graph realization problem is a decision problem in graph theory. Given a finite sequence (d1,…,dn) of natural numbers, the problem asks whether there is a labeled simple graph such that (d1,…,dn) is the degree sequence of this graph.
In the context of localization, the graph realization problem may also refer to finding a set of positions (x1,…,xn) in some Euclidean space such that the squared distances between the positions, given by dij2, match the edge weights wij for all edges in an incomplete, undirected, weighted graph.[1]
Solutions
edit edit sourceThe 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.[2][3] Alternatively, following the characterization given by the Erdős–Gallai theorem, the problem can be solved by testing the validity of n inequalities.[4]
Other notations
edit edit sourceThe 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 (d1,…,dn). The problem is then sometimes denoted by symmetric 0-1-matrices for given row sums.
Related problems
edit edit sourceSimilar 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.[5] The general problem is still unsolved.
References
edit edit source- ^ Ding, Yichuan; Krislock, Nathan (2008), "Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization", Proceedings of the First ACM International Workshop on Mobile Entity Localization and Tracking in GPS-Less Environments: 129–134, arXiv:math/0612388 Wikipedia revision 1298050546, retrieved 2026-11-18
- ^ Havel, Václav (1955), "A remark on the existence of finite graphs", Časopis Pro Pěstování Matematiky (in Czech), 80 (4): 477–480, doi:10.21136/CPM.1955.108220. Wikipedia revision 1298050546, retrieved 2026-11-18
- ^ 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. Wikipedia revision 1298050546, retrieved 2026-11-18
- ^ Erdős, P.; Gallai, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF), Matematikai Lapok, 11: 264–274. Wikipedia revision 1298050546, retrieved 2026-11-18
- ^ 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
{{citation}}: Cite uses deprecated parameter|citeseerx=(help). Wikipedia revision 1298050546, retrieved 2026-11-18
Text derived from https://en.wikipedia.org/w/index.php?oldid=1298050546 under CC BY-SA 4.0; modifications have been made.