Degree sequence of a graph: Difference between revisions
(Created page with "==Definition== ===For a finite graph=== Suppose <math>G</math> is a finite undirected graph. The '''degree sequence''' of <math>G</math> is defined as f...") |
No edit summary |
||
| Line 6: | Line 6: | ||
Note that not every non-increasing sequence arises as the degree sequence of a graph. | Note that not every non-increasing sequence arises as the degree sequence of a graph. | ||
==Related notions== | |||
* The [[degree matrix]] is informationally equivalent: it stores the degree sequence data as a graph. | |||
==Facts== | ==Facts== | ||
* [[Handshaking lemma]] states that the sum of the entries of the degree sequence is twice the number of edges. In particular, it must be even. | * [[Handshaking lemma]] states that the sum of the entries of the degree sequence is twice the number of edges. In particular, it must be even. | ||
Latest revision as of 19:16, 25 May 2014
Definition
For a finite graph
Suppose is a finite undirected graph. The degree sequence of is defined as follows: for each vertex of , calculate the degree of that vertex. We obtain a list (possibly with repetitions) of length equal to the size of the vertex set of . The degree sequence is obtained by sorting this list in descending order (i.e., we get a non-increasing, though not necessarily a strictly decreasing, sequence).
Note that not every non-increasing sequence arises as the degree sequence of a graph.
Related notions
- The degree matrix is informationally equivalent: it stores the degree sequence data as a graph.
Facts
- Handshaking lemma states that the sum of the entries of the degree sequence is twice the number of edges. In particular, it must be even.