Las gráficas de segmentos disjuntos son casi hamiltonianas.

Ponente(s): Mbe Koua Christophe Ndjatchi ., Jes\'us Lea\~nos, Luis Manuel R\'ios-Castro

Sea $G=(V,E)$ una gr\'afica simple y conexa. Recordamos que $G$ es hamiltoniana si contiene un ciclo que pasa por cada uno de sus v\'ertices. Determinar si una gr\'afica conexa dada es o no hamiltoniano es un problema cl\'asico en la teor\'ia de gr\'aficas que sigue sin resolverse. Por otro lado, sea $P$ un conjunto finito de $n\geq 1$ puntos en posici\'on general en ${\mathbb R}^2$. Sea $\mathcal{P}$ el conjunto de los $\binom{n}{2}$ segmentos con extremos en $P$. Definimos la {\em gr\'afica de segmentos disjuntos} $D(\mathcal{P})$ asociada a $\mathcal{P}$ como aquella que tiene a $\mathcal{P}$ como conjunto de v\'ertices, y dos elementos de $\mathcal{P}$ ser\'an adyacentes si y solo si son disjuntos. En esta pl\'atica, daremos una caracterizaci\'on de todas aquellas gr\'aficas de segmentos disjuntos que son hamiltonianas. Adem\'as, indicaremos los $9$ tipos de orden de $P$ para los cuales $D(P)$ no es hamiltoniana.