Given anundirected graph, a degree sequence is a monotonic nonincreasing sequence of thevertex degrees (valencies) of itsgraph vertices. The number of degree sequences for a graph of a given order is closely related tographical partitions. The sum of the elements of a degree sequence of a graph is always even due to fact that each edge connects two vertices and is thus counted twice (Skiena 1990, p. 157).

Theminimum vertex degree in agraph is denoted, and themaximum vertex degree is denoted (Skiena 1990, p. 157). Agraph whose degree sequence contains only multiple copies of a single integer is called aregular graph. A graph corresponding to a given degree sequence can be constructed in theWolfram Language usingRandomGraph[DegreeGraphDistribution[d]].

It is possible for two topologically distinct graphs to have the same degree sequence. Moreover, two distinct convex polyhedra can even have the same degree sequence for their skeletons, as exemplified by thetriangular cupola andtridiminished icosahedronJohnson solids, both of which have 8 faces, 9 vertices, 15 edges, and degree sequence (3, 3, 3, 3, 3, 3, 4, 4, 4).

A graph having a unique degree sequence may be said to beunigraphicor called a "unigraph" (Tyshkevich 2000, Barruset al.2023).

The number of distinct degree sequences for graphs of, 2, ... nodes are given by 1, 2, 4, 11, 31, 102, 342, 1213, 4361, ... (OEISA004251), compared with the total number of nonisomorphic simple undirected graphs withgraph vertices of 1, 2, 4, 11, 34, 156, 1044, ... (OEISA000088). The first order having fewer degree sequences than number of nonisomorphic graphs is therefore. For the graphs illustrated above, the degree sequences are given in the following table.

1
2	,
3	,,,
4	,,,,
	,,,,
	,,

The possible sums of elements for a degree sequence of order are 0, 2, 4, 6, ...,.

A degree sequence is said to be-connected if there exists some-connected graph corresponding to the degree sequence. For example, while the degree sequence is 1- but not 2-connected, is 2-connected.

See also

Explore with Wolfram|Alpha

More things to try:

• graph properties
• 7.5% of .95
• find features of shark image with radius 0.5

References

Referenced on Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Degree Sequence."FromMathWorld--A Wolfram Resource.https://mathworld.wolfram.com/DegreeSequence.html

Subject classifications