Realizaciones lineales de listas

Ponente(s): Adrian Vazquez Avila

Consideremos a la gráfica completa $K_n$ de $n$ vértices, donde sus vértices están etiquetados sobre el conjunto $\{0, 1,\ldots, n-1\}$. La longitud de una arista $xy$, donde $x,y\in V(K_n)$, se define como $\ell(x,y)=\min\{|y-x|, n-|y-x|\}$. Dada una trayectoria $P=(x_0, x_1, \ldots, x_k)$, la lista de longitudes de $P$, $\ell(P)$, es el multiconjunto de longitudes de todas las aristas de $P$, considerando sus multiplicidades. Una realización lineal de una lista $L$, con $n-1$ enteros positivos que no exceden a $n-1$, es una trayectoria Hamiltoniana $P=(x_0, x_1,..., x_{n-1})$ de $K_n$ tal que $L=\{|x_i-x_{i+1}|:i=0,\ldots,n-2\}$. En esta charla expondré algunos resultados sobre realizaciones lineales cuyo conjunto subyacente es de tamaño 3, 4 y 5.