Secuencias de grados de realización única

Abstract

[en] A positive integer sequence is graphic if it is the degree sequence of a simple graph. We say this graph realizes the sequence. In addition, if up to isomorphism only one graph realizes the sequence, the sequence is a graphic sequence with unique realization. Throughout the work we will analize several theorems and algorithms used to identify this type of sequences. Following that, we will see code done by me to make it easier to find the desired sequences. Finally, I will use all the previous work to create the following lower bound of the number of single realization graphic sequences of length $n$.

Teorema. Be $p(i)$ the number of partitions of the integer $i$. Given an integer $n \geq 7$. - if $n$ is odd, the number of graphic sequences with unique realization verifies: $$ u(n) \geq 2^{n-5} u(5)+\sum_{i=6}^n 2^{n-i+1} p(i)-\sum_{i=6}^n i 2^{n-i}-\sum_{i=0}^{\frac{n-7}{2}}\left(4^{i+1}+3 \cdot 4^i\right) $$ - if $n$ is even, the number of graphic sequences with unique realization verifies: $$ u(n) \geq 2^{n-5} u(5)+\sum_{i=6}^n 2^{n-i+1} p(i)-\sum_{i=6}^n i 2^{n-i}-\sum_{i=6}^{\frac{n-8}{2}}\left(2^{2 i+1}+6 \cdot 4^i\right)-2^{n-5} $$

[es] Una secuencia de enteros positivos es gráfica si esta es la secuencia de grados de un grafo simple. Decimos que este grafo realiza la secuencia. Además, si solo un grafo y sus grafos isomorfos realizan dicha secuencia, la secuencia es una secuancia gráfica con realización única. A lo largo de este trabajo analizaremos diferentes teoremas y algoritmos parar identificar este tipo de secuencias. Posteriormente, veremos un código elaborado por mi mismo para encontrar las secuencias deseadas. Finalmente, usaré todo el trabajo previo para crear la siguiente cota inferior del número de secuencias gráficas con realización única de longitud $n$.

Teorema. Sea $p(i)$ el número de particiones del entero $i$. Dado un entero $n \geq 7$. - Sin es impar, el número de secuencias de grados gráficas con realización única verifica: $$ u(n) \geq 2^{n-5} u(5)+\sum_{i=6}^n 2^{n-i+1} p(i)-\sum_{i=6}^n i 2^{n-i}-\sum_{i=0}^{\frac{n-7}{2}}\left(4^{i+1}+3 \cdot 4^i\right) $$ - Si n es par, el número de secuencias de grados gráficas con realización única verifica: $$ u(n) \geq 2^{n-5} u(5)+\sum_{i=6}^n 2^{n-i+1} p(i)-\sum_{i=6}^n i 2^{n-i}-\sum_{i=6}^{\frac{n-8}{2}}\left(2^{2 i+1}+6 \cdot 4^i\right)-2^{n-5} $$