Browsing by Author "Stein, Maya"
Now showing items 21-26 of 26
-
(Universidad de Chile, 2016)Un conjunto de vértices de un grafo se dice convexo si contiene a los vértices de todos los caminos mínimos entre sus vértices. El problema de determinar si un grafo tiene una partición en p conjuntos convexos es NP-completo, ...
-
(Universidad de Chile, 2023)En esta tesis se trabaja con los siguientes conceptos de teoría de grafos: Dado un grafo $G$ y un entero positivo $p$, la potencia exacta $p$-ésima de $G$ denotada por $\exact{G}{p}$ es el grafo con el mismo conjunto de ...
-
(SIAM PUBLICATIONS, 2010)A connected graph G is called t-perfect if its stable set polytope is determined by the non-negativity, edge and odd-cycle inequalities. More- over, G is called strongly t-perfect if this system is totally dual inte- gral. ...
-
(Universidad de Chile, 2021)Una doble estrella $S(n,m)$ es el grafo obtenido a partir de una estrella con $n$ hojas y otra estrella con $m$ hojas al unir sus centros con una arista. Sea $R(S(n,m))$ el número de Ramsey, definido como el mínimo $N$ tal ...
-
(Universidad de Chile, 2021)En esta tesis se estudia una serie de problemas en combinatoria extremal y probabilista relacionados a árboles y palabras. En la primera parte de este trabajo se estudian qué condiciones debe cumplir un grafo para que ...
-
(Universidad de Chile, 2018)En 1995 Komlós, Sárközy y Szemerédi probaron que para cualquier $\delta>0$ y cualquier entero positivo $\Delta$, todo grafo $G$ de orden $n$, con $n$ suficientemente grande, que satisfaga $\delta(G)\geq (1+\delta)\frac{n}{2}$, ...
