Degree Sequence

Given an undirected graph, a degree sequence is a monotonic nonincreasing sequence of the vertex degrees (valencies) of its graph vertices. The number of degree sequences for a graph of a given order is closely related to graphical 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).

The minimum vertex degree in a graph  is denoted , and the maximum vertex degree is denoted  (Skiena 1990, p. 157). A graph whose degree sequence contains only multiple copies of a single integer is called a regular graph. A graph corresponding to a given degree sequence  can be constructed in the Wolfram Language using RandomGraph[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 the triangular cupola and tridiminished icosahedron Johnson solids, both of which have 8 faces, 9 vertices, 15 edges, and degree sequence (3, 3, 3, 3, 3, 3, 4, 4, 4).

The number of distinct degree sequences for graphs of , 2, ... nodes are given by 1, 2, 4, 11, 31, 102, 342, 1213, 4361, ... (OEIS A004251), compared with the total number of nonisomorphic simple undirected graphs with  graph vertices of 1, 2, 4, 11, 34, 156, 1044, ... (OEIS A000088). 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	{0}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline8.svg" style="height:22px; width:22px" />
2	{0,0}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline9.svg" style="height:22px; width:43px" />, {1,1}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline10.svg" style="height:22px; width:43px" />
3	{0,0,0}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline11.svg" style="height:22px; width:64px" />, {1,1,0}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline12.svg" style="height:22px; width:64px" />, {2,1,1}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline13.svg" style="height:22px; width:64px" />, {2,2,2}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline14.svg" style="height:22px; width:64px" />
4	{0,0,0,0}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline15.svg" style="height:22px; width:85px" />, {1,1,0,0}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline16.svg" style="height:22px; width:85px" />, {2,1,1,0}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline17.svg" style="height:22px; width:85px" />, {2,2,2,0}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline18.svg" style="height:22px; width:85px" />,
	{3,2,2,1}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline19.svg" style="height:22px; width:85px" />, {3,3,2,2}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline20.svg" style="height:22px; width:85px" />, {3,3,3,3}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline21.svg" style="height:22px; width:85px" />, {1,1,1,1}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline22.svg" style="height:22px; width:85px" />,
	{2,2,1,1}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline23.svg" style="height:22px; width:85px" />, {2,2,2,2}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline24.svg" style="height:22px; width:85px" />, {3,1,1,1}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline25.svg" style="height:22px; width:85px" />

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 {1,2,1}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline30.svg" style="height:22px; width:64px" /> is 1- but not 2-connected, {2,2,2}" src="https://mathworld.wolfram.com/images/equations/DegreeSequence/Inline31.svg" style="height:22px; width:64px" /> is 2-connected.

---

REFERENCES

Ruskey, F. "Information on Degree Sequences." http://www.theory.csc.uvic.ca/~cos/inf/nump/DegreeSequences.html.

Ruskey, F.; Cohen, R.; Eades, P.; and Scott, A. "Alley CATs in Search of Good Homes." Congres. Numer. 102, 97-110, 1994.

Skiena, S. "Realizing Degree Sequences." §4.4.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 157-160, 1990.

Sloane, N. J. A. Sequence A004251/M1250 in "The On-Line Encyclopedia of Integer Sequences."

اخر الاخبار

اخبار العتبة العباسية المقدسة

متحف الكفيل: المكتبة المتحفية توفر مصادر وكتبًا نادرة باللغتين العربية والإنكليزية

الأمانتان العامتان للعتبتين المقدستين تقيمان مجلس الفاتحة على روح العلامة السيد محمد علي بحر العلوم

شعبة الحرم الشريف تستبدل ستائر أبواب حرم مرقد أبي الفضل العباس (عليه السلام)

وفد الأمانة العامة للعتبة العباسية المقدسة يشارك في مجلس فاتحة السيد محمد علي بحر العلوم (قدس سره)

المزيد

الآخبار الصحية

هل يمكن الاعتماد على "ChatGPT" في الحصول على نصائح صحية؟

قبل أي نشاط رياضي.. هذه الفاكهة ينصح بها الخبراء

استخدام القنب للعلاج.. دراسة تحذر من من "جنون العظمة" ؟!

غالبية الناس ينظفون أسنانهم خطأ.. إليك الطريقة الصحيحة

المزيد

الآخبار التكنلوجية

نصائح لإطالة عمر بطارية السيارة وضمان أدائها الأمثل

الرياض تحتضن مونديال الرياضات الإلكترونية بدعم stc

"ستارشيب" ينطلق في رحلة تجريبية ويسقط بالمحيط الهندي !

شركة جديدة.. خطة ماسك لمنافسة مايكروسوفت في الذكاء الاصطناعي

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength