Seqüència de graus

Dos grafos no isomorfos pero en igual seqüència de graus (3,2,2,2,2,1,1,1).

En el camp matemàtic de la teoria de grafos, una seqüència de graus també anomenada successió gràfica o llista de graus d'un grafo no dirigit és una seqüència de números, els quals són graus dels vèrtiços del grafo.

La llista de graus és un invariante (topològic) d'un grafo, encara que dos grafos en igual llista de graus no són necessàriament isomorfos.

Grafo G(V,A)	Conjunts	Seqüència de graus
	V = { 1, 2, 3, 4, 5, 6 } A = { {1,1}, {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} }	(4,3,3,3,2,1)

Problema de la seqüència de sancers gràfica

Grafos simples

Un problema interessant és determinar si una seqüència de sancers no negatius qualsevol és o no gràfica, és dir, és una seqüència de graus d'un grafo (simple). Erdős i Gallai en 1960 resolen el problema en el seu teorema d'existència:

Mentres que Havel en 1955 i Hakimi en 1962 nos entreguen una teorema de construcció que justifica el Algoritme de Havel-Hakimi per a construir un grafo a partir d'una seqüència de graus.

Una seqüència de sancers $d_1\ge d_2\ge \mathrm{...}\ge d_v\ge 0$ és gràfica sí, i només sí també ho és la llista: $d_2-1,d_3-1,\mathrm{...},d_{d_1+1}-1,d_{d_1+2},\mathrm{...},d_v$, que resulta d'eliminar el primer element i restar una unitat als següents $d_1$ valors de la llista.

Multigrafos

El problema de la seqüència de sancers gràfica per a multigrafos o pseudografos és: donada una seqüència de sancers no negatius, determinar si és o no (multi)gràfica, és dir, és una seqüència de graus d'un psedugrafo o multigrafo. Hakimi en 1962, nos entrega un resultat:

Una seqüència de sancers $d_1\ge d_2\ge \mathrm{...}\ge d_n$ a on $n\ge 2$ és multigráfica (o pseudográfica) sí, i només sí la suma $\sum _{i=1}^k{d}_i$ és parell i $d_1\le d_2+\mathrm{...}+d_n$.