Carregant...
Tipus de document
Treball de fi de grauData de publicació
Llicència de publicació
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/211800
Secuencias de grados de realización única
Títol de la revista
Autors
Director/Tutor
ISSN de la revista
Títol del volum
Recurs relacionat
Resum
[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}
$$
Descripció
Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2024, Director: Kolja Knauer
Matèries (anglès)
Citació
Col·leccions
Citació
ROVIRA CORTÉS, Ramón. Secuencias de grados de realización única. [consulta: 24 de gener de 2026]. [Disponible a: https://hdl.handle.net/2445/211800]