Degree (graph Theory) - Degree Sequence

The degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees; for the above graph it is (5, 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. 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 multigraph. The construction of such a graph is straightforward: connect vertices with odd degrees in pairs by a matching, and fill out the remaining even degree counts by self-loops. The question of whether a given degree sequence can be realized by a simple graphs is more challenging. The Erdős–Gallai theorem states that a non-increasing sequence of n numbers di (for i = 1,...,n) is the degree sequence of a simple graph if and only if the sum of the sequence is even and

For instance, the sequence (3, 3, 3, 1) is not the degree sequence of a simple graph; it satisfies the Erdős–Gallai inequality when k is 1, 2, or 4 but not when k = 3.

Havel (1955), and later, Hakimi (1962) proved that (d1, d2, ..., dn) is a degree sequence of a simple graph if and only if (d2 − 1, d3 − 1, ..., dd1+1 − 1, dd1+2, dd1+3, ..., dn) is. This fact leads to a simple algorithm for finding a simple graph that has a given realizable degree sequence:

  1. Begin with a graph with no edges.
  2. Maintain a list of vertices whose degree requirement has not yet been met in non-increasing order of residual degree requirement.
  3. Connect the first vertex to the next d1 vertices in this list, and then remove it from the list. Re-sort the list and repeat until all degree requirements are met.

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

Read more about this topic:  Degree (graph Theory)

Famous quotes containing the words degree and/or sequence:

    “I would rather be exposed to the inconveniences attending too much liberty than those attending too small a degree of it.”
    —Thomas Jefferson (1743–1826)

    “Reminiscences, even extensive ones, do not always amount to an autobiography.... For autobiography has to do with time, with sequence and what makes up the continuous flow of life. Here, I am talking of a space, of moments and discontinuities. For even if months and years appear here, it is in the form they have in the moment of recollection. This strange form—it may be called fleeting or eternal—is in neither case the stuff that life is made of.”
    —Walter Benjamin (1892–1940)