Gemelos de árboles con una cantidad contable de ends

Abstract

Dos grafos son gemelos si son mutuamente subgrafos entre sí. En grafos finitos la única forma de que dos grafos sean mutuamente subgrafos entre sí es que sean isomorfos. Sin embargo, en grafos infinitos existen grafos que se incluyen mutuamente y no isomorfos entre sí. Bonato y Tardif [3] se preguntaron por la cantidad de gemelos que puede tener un grafo. La conjetura de alternativa en árboles plantea que si un árbol tiene gemelos no isomorfos a él, entonces tiene infinitos gemelos. En el presente trabajo se presenta una demostración de la conjetura para árboles localmente finitos con una cantidad contable de ends. Se comienza realizando una revisión general de los conceptos y teoremas de grafos infinitos. Se introducen los conceptos básicos de grafos infinitos (rayo, doble rayo, end etc). Luego se estudia también una topología definible para un grafo infinito, que describe de mejor manera el grafo y sus ends que es de relevancia en la demostración dada posteriormente. Posteriormente se estudian los conceptos, definiciones y teoremas propios de la conjetura. Se revisarán los trabajos hechos hasta ahora, las ideas que han surgido a partir de intentos para demostrar la conjetura y la descripción de un grafo con propiedades interesantes. A continuación se estudia en detalle la relación subgrafo en grafos infinitos. Se introduce el concepto de morfismo y se muestra su relación con los conceptos de subgrafo e isomorfismo. También se estudia el grupo de automorfismos del doble rayo y de árboles finitos. Se mostrará además una forma de definir isomorfismos entre árboles infinitos localmente finitos a partir de isomorfismos locales. También se estudiará la construcción de isomorfismos definidos por componentes. Luego, se demuestra la conjetura para árboles con una cantidad finita de ends. Primero se demuestra la conjetura para árboles con exactamente un end, luego con exactamente dos ends y finalmente para árboles con más de 2 ends. Finalmente, se demuestra la conjetura para árboles con una cantidad infinita contable de ends. Se introduce el concepto de centro-end y a partir de éste se demostrará una extensión de un teorema dado por Halin [7] para árboles con una cantidad contable de ends. Este resultado fue dado por Polat y Sabidussi [9] para automorfismos, se presenta una demostración alternativa que también abarca endomorfismos. Usando esta extensión se demuestra la conjetura. Se define el concepto de ecuación gráfica, que junto con el teorema extendido de Halin permiten demostrar la conjetura en el caso más difícil.