Vipul at 19:16, 25 May 2014

2014-05-25T19:16:46Z

← Older revision		Revision as of 19:16, 25 May 2014
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.

Vipul: Created page with "==Definition== ===For a finite graph=== Suppose $G$ is a finite undirected graph. The '''degree sequence''' of $G$ is defined as f..."

2012-05-28T17:38:38Z

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..."

New page

==Definition==

===For a finite graph===

Suppose <math>G</math> is a [[finite graph|finite]] [[undirected graph]]. The '''degree sequence''' of <math>G</math> is defined as follows: for each vertex of <math>G</math>, calculate the [[degree of a vertex|degree]] of that vertex. We obtain a list (possibly with repetitions) of length equal to the size of the vertex set of <math>G</math>. 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.

==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.

Degree sequence of a graph - Revision history

Vipul at 19:16, 25 May 2014

Vipul: Created page with "==Definition== ===For a finite graph=== Suppose G is a finite undirected graph. The '''degree sequence''' of G is defined as f..."

Vipul: Created page with "==Definition== ===For a finite graph=== Suppose $G$ is a finite undirected graph. The '''degree sequence''' of $G$ is defined as f..."