# Graph realization problem

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Graph_realization_problem
> Markdown URL: https://mediated.wiki/source/Graph_realization_problem.md
> Source: https://en.wikipedia.org/wiki/Graph_realization_problem
> Source revision: 1298050546
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Existence of a graph with a degree sequence}}
thumb|Two non-isomorphic graphs realized from the degree sequence (3, 2, 2, 2, 2, 1, 1, 1).

The '''graph realization problem''' is a [decision problem](/source/decision_problem) in [graph theory](/source/graph_theory). Given a finite sequence <math>(d_1,\dots,d_n)</math> of natural numbers, the problem asks whether there is a labeled [simple graph](/source/Graph_(discrete_mathematics)) such that <math>(d_1,\dots,d_n)</math> is the [degree sequence](/source/degree_sequence) of this graph.

In the context of localization, the '''graph realization problem''' may also refer to finding a set of positions <math>(x_1,\dots,x_n)</math> in some Euclidean space such that the squared distances between the positions, given by <math>d^2_{ij}</math>, match the edge weights <math>w_{ij}</math> for all edges in an incomplete, undirected, weighted graph.<ref>{{citation
| last1= Ding | first1= Yichuan | last2= Krislock | first2= Nathan
| title= Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization 
| year= 2008
| journal= Proceedings of the First ACM International Workshop on Mobile Entity Localization and Tracking in GPS-Less Environments
| pages= 129–134
| arxiv= math/0612388 }}</ref>
==Solutions==
The problem can be solved in [polynomial time](/source/polynomial_time). One method of showing this uses the [Havel–Hakimi algorithm](/source/Havel%E2%80%93Hakimi_algorithm) constructing a special solution with the use of a [recursive algorithm](/source/Recursion_(computer_science)).<ref>{{citation
| last= Havel
| first= Václav
| authorlink =V. J. Havel
| year = 1955
| title = A remark on the existence of finite graphs
| language = Czech
| journal = Časopis Pro Pěstování Matematiky
| volume = 80
| issue= 4
| pages = 477–480
| doi= 10.21136/CPM.1955.108220
| url = http://eudml.org/doc/19050
| doi-access = free
}}.</ref><ref>{{citation
 | last = Hakimi | first = S. L. | authorlink = S. L. Hakimi
 | journal = Journal of the Society for Industrial and Applied Mathematics
 | mr = 0148049
 | pages = 496–506
 | title = On realizability of a set of integers as degrees of the vertices of a linear graph. I
 | volume = 10
 | issue = 3 | year = 1962| doi = 10.1137/0110037 | hdl = 10338.dmlcz/128153
 | hdl-access = free
 }}.</ref> Alternatively, following the characterization given by the [Erdős–Gallai theorem](/source/Erd%C5%91s%E2%80%93Gallai_theorem), the problem can be solved by testing the validity of <math>n</math> inequalities.<ref>{{citation
 | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
 | last2 = Gallai | first2 = T. | author2-link = Tibor Gallai
 | journal = Matematikai Lapok
 | pages = 264–274
 | title = Gráfok előírt fokszámú pontokkal
 | url = http://www.renyi.hu/~p_erdos/1961-05.pdf
 | volume = 11
 | year = 1960}}.</ref>

==Other notations==
The problem can also be stated in terms of [symmetric matrices](/source/symmetric_matrix) of zeros and ones. The connection can be seen if one realizes that each graph has an [adjacency matrix](/source/adjacency_matrix) where the column sums and row sums correspond to <math>(d_1,\ldots,d_n)</math>. The problem is then sometimes denoted by ''symmetric 0-1-matrices for given row sums''.

==Related problems==
Similar problems describe the [degree sequence](/source/bipartite_graph)s of [simple bipartite graphs](/source/bipartite_graph) or the [degree sequence](/source/directed_graph)s of [simple directed graphs](/source/directed_graph). The first problem is the so-called [bipartite realization problem](/source/bipartite_realization_problem). The second is known as the [digraph realization problem](/source/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](/source/polynomial-time_approximation_scheme) for the degree sequences of [regular graph](/source/regular_graph)s by Cooper, Martin, and Greenhill.<ref>{{citation
 | last1 = Cooper | first1 = Colin
 | last2 = Dyer | first2 = Martin | author2-link = Martin Dyer
 | last3 = Greenhill | first3 = Catherine | author3-link = Catherine Greenhill
 | doi = 10.1017/S0963548306007978
 | issue = 4
 | journal = [Combinatorics, Probability and Computing](/source/Combinatorics%2C_Probability_and_Computing)
 | mr = 2334585
 | pages = 557–593
 | title = Sampling regular graphs and a peer-to-peer network
 | volume = 16
 | year = 2007| citeseerx = 10.1.1.181.597
 }}.</ref> The general problem is still unsolved.

==References==
{{reflist}}

{{DEFAULTSORT:graph realization problem}}
Category:Computational problems in graph theory

---
Adapted from the Wikipedia article [Graph realization problem](https://en.wikipedia.org/wiki/Graph_realization_problem) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Graph_realization_problem?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.