Free Articles: Graphic sequence

Degree (graph theory)

In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex $v$ is denoted $deg(v).$ The maximum degree of a graph G, denoted by Δ(G), and the minimum degree of a graph, denoted by δ(G), are the maximum and minimum degree of its vertices. In the graph on the right, the maximum degree is 3 and the minimum degree is 0. In a regular graph, all degrees are the same, and so we can speak of the degree of the graph.

Handshaking lemma

The degree sum formula states that, given a graph $G = (V, E)$ ,

$\sum_{v \in V} \deg(v) = 2|E|\, .$

The formula implies that in any graph, the number of vertices with odd degree is even. This statement (as well as the degree sum formula) is known as the handshaking lemma. The latter name comes from a popular mathematical problem, to prove that in any group of people the number of people who have shaken hands with an odd number of other people from the group is even.

Degree sequence

The degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees; for the above graph it is (3, 3, 3, 2, 2, 1, 0). The degree sequence is a graph invariant so isomorphic graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a graph; in some cases, non-isomorphic graphs have the same degree sequence.

The degree sequence problem is the problem of finding some or all graphs with the degree sequence being a given non-increasing sequence of positive integers. (Trailing zeroes may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the graph.) A sequence which is the degree sequence of some graph, i.e. for which the degree sequence problem has a solution, is called a graphic or graphical sequence.

The problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of graph enumeration.

As a consequence of the degree sum formula, any sequence with an odd sum, such as (3, 3, 1), cannot be realized as the degree sequence of a graph. The converse is also true: if a sequence has an even sum, it is the degree sequence of a graph. The construction of such a graph is simple: connect odd vertices in pairs, and fill with self-loops.

Often one wishes to search for simple graphs, making the degree sequence problem more challenging. Obviously the sequence (8, 4) is not the degree sequence of a simple graph, since we would have the contradiction Δ(G) > (number of vertices − 1). The sequence (3, 3, 3, 1) is also not the degree sequence of a simple graph, but in this case the reason is less obvious. Finding general criteria for degree sequences of simple graphs is a classical problem; solutions have been offered by Erdős and Gallai (1960), V. J. Havel (1955) and S. L. Hakimi (1961), S. A. Choudum and Sierksma et al. (1991).

For example, the Erdős–Gallai theorem states that a non-increasing sequence of n numbers d_i (for i = 1,...,n) is the degree sequence of a simple graph if and only if the sum of the sequence is even and

$\sum_{i=1}^{k}d_i \leq k(k-1) + \sum_{i=k+1}^n \min(d_i,k) \quad \text{for } k \in \{1,\dots,n\} \, .$

Havel and Hakimi proved that (d₁, d₂, ..., d_n) is a degree sequence of a simple graph if and only if (d₂ − 1, d₃ − 1, ..., d_d₁+1 − 1, d_d₁+2, d_d₁+3, ..., d_n) is. This fact leads to a simple algorithm (the Havel-Hakimi algorithm) for realizing a simple graph with a given realizable degree sequence: Begin with a graph with no edges. Maintain a list of vertices whose degree requirement has not yet been met in non-increasing order of residual degree requirement. Connect the first vertex to the next d₁ vertices in this list, and then remove it from the list. Re-sort the list and repeat until all degree requirements are met.

Special values

Global properties

Notes

References

Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/.
G. Sierksma and H. Hoogeveen, "Seven criteria for integer sequences being graphic, " Journal of Graph Theory 15, No. 2 (1991) 223–231.

Retrieved from : http://en.wikipedia.org/wiki/Degree_(graph_theory)#Degree_sequence

Free Articles

2011-05-21

Graphic sequence