La conjetura de Sheehan en teoría de grafos

DEPARTAMENTO DE GEOMETRÍA Y TOPOLOGÍA LA CONJETURA DE SHEEHAN EN TEORÍA DE GRAFOS Sabrina Fortes Lorenzo LA CONJETURA DE SHEEHAN EN TEORÍA DE GRAFOS Sabrina Fortes Lorenzo Memoria presentada como parte de los requisitos para la obtención del título de Grado en Matemáticas por la Universidad de Sevilla. Tutorizada por Prof. Ramón Jesús Flores Díaz Profª. María Nieves Atienza Martínez Índice general Resumen 1 English Abstract 3 Introducción 5 1. PRELIMINARES 7 1.1. Definiciones, notación y resultados previos . . . . . . . . . . . . . . . 7 2. LA CONJETURA DE SHEEHAN 13 2.1. Establecimiento de la conjetura de Sheehan . . . . . . . . . . . . . . . 13 2.2. Marcohistórico............................... 13 3. EXTENSIÓN DE LA CONJETURA A CUALQUIER REGULARIDAD 15 3.1. Caso particular de las regularidades pares. . . . . . . . . . . . . . . . 15 3.2. La 3-regularidad y su extensión a toda regularidad impar . . . . . . . 18 3.2.1. Caso particular de la 3-regularidad . . . . . . . . . . . . . . . 18 3.2.2. Extensión para toda regularidad impar . . . . . . . . . . . . . 21 4. PRUEBA PARA REGULARIDADES SUFICIENTEMENTE GRANDES 25 ii la conjetura de sheehan en teoría de grafos 4.1. LacotadeThomassen........................... 25 4.2. Mejoradelacota ............................. 29 5. GRAFOS BIRREGULARES DE REGULARIDAD 4 Y 14 35 5.1. Resultados auxiliares . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2. Demostración del teorema principal. Construcción. . . . . . . . . . . 39 6. OTROS RESULTADOS RELACIONADOS CON LA CONJETURA DE SHEEHAN 45 6.1. Grafos hamiltonianos y grado 3 . . . . . . . . . . . . . . . . . . . . . 45 6.2. Aproximación asintótica a la conjetura de Sheehan . . . . . . . . . . 46 6.3. Ejemplos de grafos 3-conexos únicamente hamiltonianos . . . . . . . 46 6.4. Bondy-Jackson............................... 46 6.5. Grafosbipartitos.............................. 47 6.6. Otros grafos únicamente hamiltonianos . . . . . . . . . . . . . . . . . 47 Resumen La conjetura de Sheehan en teoría de grafos afirma la inexistencia de grafos hamiltonianos 4-regulares con un único ciclo hamiltoniano. El objetivo de este trabajo es presentar la conjetura y realizar una recorrido por los resultados parciales que se han ido obteniendo, los ejemplos de interés que han generado los intentos de refutarla, y otros resultados relacionados. English Abstract Sheehan’s conjecture in graph theory asserts the non-existence of 4-regular Hamiltonian graphs with a unique Hamiltonian cycle. The goal of this work is to introduce the conjecture and provide an overview of the partial results that have been obtained, the interesting examples that have arisen from attempts to refute it, and other related findings. 10 la conjetura de sheehan en teoría de grafos Definición 1.13 [Recorrido euleriano].Un recorrido euleriano en un grafo 𝐺= (𝑉 , 𝐴)es un camino que pasa por cada arista de 𝐴una única vez. Un circuito euleriano es un recorrido euleriano que empieza y acaba en el mismo vértice. Definición 1.14 [Grafo euleriano].Un grafo es euleriano si tiene un circuito euleriano. Definición 1.15 [Camino hamiltoniano].Un camino hamiltoniano en un grafo 𝐺= (𝑉 , 𝐴)es un camino que pasa por todos los vértices de G una única vez. Si empieza y acaba en el mismo vértice es un ciclo hamiltoniano. Definición 1.16 [Grafo hamiltoniano].Un grafo es hamiltoniano si tiene un ciclo hamiltoniano. Definición 1.17 [Grafo únicamente hamiltoniano].Llamamos grafo únicamente hamiltoniano a un grafo que contiene exactamente un ciclo hamiltoniano. Definición 1.18 [Grafo conexo].Un grafo 𝐺= (𝑉 , 𝐴)es conexo si ∀𝑢, 𝑣 ∈𝑉existe un camino que los conecta. Teorema 1.1 [Teorema 4.1 [4]].Un grafo conexo 𝐺tiene un circuito euleriano ⇐⇒ ∀𝑣∈𝑉 , 𝛿(𝑣)es par. Definición 1.19 [Subgrafo].Dado 𝐺= (𝑉 , 𝐴)decimos que 𝐺′= (𝑉′, 𝐴′)es subgrafo de 𝐺si 𝑉′⊆ 𝑉 y𝐴′⊆ 𝐴. Si además 𝑉′=𝑉a𝐺′se le llama subgrafo recubridor. Si 𝑉′⊆ 𝑉 y𝐴′= {𝑢𝑣 ∈𝐴|𝑢, 𝑣 ∈𝑉′}se dice que 𝐺′es un subgrafo de 𝐺inducido por 𝑉′. En este caso también se suele decir que 𝐺′es lleno en 𝐺. Definición 1.20 [Homomorfismo de grafos].Dados dos grafos simples 𝐺= (𝑉 , 𝐴) y𝐺′= (𝑉′, 𝐴′), un homomorfismo entre 𝐺y𝐺′es una aplicación 𝜙∶𝑉←→ 𝑉′que conserva las adyacencias, es decir, ∀𝑢𝑣 ∈𝐴ha de verificarse 𝜙(𝑢)𝜙(𝑣) ∈ 𝐴′. Definición 1.21 [Isomorfismo de grafos].Un homomorfismo entre 𝐺y𝐺′biyectivo cuyo inverso es un homomorfismo entre 𝐺′y𝐺se llama isomorfismo. Definición 1.22 [k-factor].Sea 𝑘≥1,un k-factor es un subgrafo recubridor de G en el que todos los vértices tienen grado 𝑘. Definición 1.23 [Emparejamiento o matching].Un matching de un grafo 𝐺= (𝑉 , 𝐴)es un subconjunto 𝑀 ⊆ 𝐴 de aristas independientes, es decir, sin vértices en común. Se dice que un vértice 𝑣∈𝑉está saturado si alguna arista del matching es incidente en él. Un matching 𝑀es máximo si contiene el número máximo de aristas posibles. Un matching 𝑀es maximal si al añadirle cualquier arista que no pertenece a 𝑀deja 1. preliminares 11 de ser un apareamiento. Un matching 𝑀es perfecto si cubre todos los vértices del grafo. Es decir, cada vértice de 𝐺está saturado bajo el matching. Figura 1.1: Ejemplos de k-factor. Nota 1.4.Nótese que un matching perfecto 𝑀de un grafo 𝐺(𝑉 , 𝐴)es similar a un 1-factor de G. La diferencia es que 𝑀está formado exclusivamente por aristas mientras que el segundo es un subgrafo de G. Existe una estrecha relación entre los matchings y los grafos bipartitos. En 1986, P. Hall encontró una condición suficiente y necesaria para encontrar un matching que cubra al menos uno de los conjuntos de vértices de un grafo bipartito. El resultado viene dado por el siguiente teorema que no demostraremos. Teorema 1.2 [Teorema del matrimonio de Hall [12]].Sea 𝐺[𝐴, 𝐵]un grafo bipartito, entonces G tiene un matching que satura todos los vértices de A ⇐⇒ ∀𝑆 ⊆ 𝐴 se tiene |𝑆|≤|𝑁𝐺(𝑆)|. ⊳Corolario 1.1. Sea 𝐺[𝐴, 𝐵]un grafo bipartito k-regular con 𝑘≥1. Entonces 𝐺 tiene un matching perfecto. Demostración. Sea 𝐺[𝐴, 𝐵]un grafo bipartito k-regular con 𝑘≥1. Sean 𝑆 ⊆ 𝐴 y𝐺′el subgrafo bipartito de 𝐺inducido por la partición [𝑆, 𝑁𝐺(𝑆)]. Supongamos que |𝑁𝐺(𝑆)|<|𝑆|. 12 la conjetura de sheehan en teoría de grafos Como cada vértice de S tiene grado 𝑘,𝐺′tendrá ∑ 𝑣∈𝑆 𝛿(𝑣) = 𝑘|𝑆|aristas. Así, al repartirlas entre |𝑁𝐺(𝑆)|vértices se tiene 𝑘|𝑆| |𝑁𝐺(𝑆)|> 𝑘 ya que por hipótesis se tiene |𝑁𝐺(𝑆)|<|𝑆|. Es decir, la media de los grados en 𝑁𝐺(𝑆) es mayor que 𝑘, lo cual es absurdo puesto que 𝛿(𝑣)≤𝑘∀𝑣∈𝐺′. De este modo concluimos que ha de ser |𝑁𝐺(𝑆)|≥|𝑆|∀𝑆 ⊆ 𝐴 y por el Teorema 1.2 sabemos entonces que 𝐺tiene un matching 𝑀que satura todo vértice de 𝐴. Finalmente, supongamos que 𝑀no es perfecto, es decir, 𝑀no satura todo vértice de 𝐺. Entonces debe ocurrir |𝐵|>|𝐴|. Sin embargo, como 𝐺es bipartito y k-regular el número de aristas viene dado por 𝑘|𝐴|=𝑘|𝐵|⇐⇒ |𝐴|=|𝐵|, lo que nos lleva a una contradicción. Se tiene por tanto que 𝑀ha de ser un matching perfecto. □ Figura 1.2: Representación gráfica para la idea de la demostración del Corolario 1.1 2 LA CONJETURA DE SHEEHAN 2.1 Establecimiento de la conjetura de Sheehan En 1975, J. Sheehan formuló una conjetura acerca de la existencia de un segundo ciclo hamiltoniano en grafos hamiltonianos de regularidad 4. La trascendencia de dicha conjetura reside realmente en el resultado que se desprende de ella y damos en forma de otra conjetura. Conjetura 2.1 [Conjetura de Sheehan [19]].Sea G un grafo 4-regular, si G contiene un ciclo hamiltoniano entonces contiene al menos dos. Si la conjetura de Sheehan es cierta, se puede extender el resultado para todo grafo hamiltoniano con regularidad mayor que 2, de modo que se tiene lo siguiente: Conjetura 2.2. Para cualquier entero 𝑑≥3, todo grafo hamiltoniano d-regular contiene al menos un segundo ciclo hamiltoniano. 2.2 Marco histórico. En el campo de la teoría de grafos, los grafos hamiltonianos han sido un tema de gran interés durante décadas. Sin embargo, a pesar de los avances en este área, todavía existen grandes interrogantes sin respuesta y problemas no resueltos. En el estudio de la posible existencia de un segundo ciclo hamiltoniano en grafos de los que se conoce que ya contienen uno, aún queda mucho por descubrir. 14 la conjetura de sheehan en teoría de grafos El resultado más antiguo relacionado con este problema se atribuye al matemático Cedric Smith, aunque no fue conocido hasta 1946, gracias a un artículo de William Tutte en el cual se probaba que ningún grafo hamiltoniano 3-regular podía ser únicamente hamiltoniano [24]. No fue hasta treinta años más tarde que Sheehan lanzó su conjetura en este contexto. La idea de que todo grafo hamiltoniano 4-regular posea al menos un segundo ciclo hamiltoniano sigue sin haber sido probada hasta día de hoy. Dicha conjetura es el tema de interés de este trabajo y será el nexo de relación entre todos los resultados aquí presentados. En 1978, Thomason publica una nueva demostración para lo ya conocido por el resultado de Smith-Tutte y además presenta una forma de extender estas conclusiones a grafos hamiltonianos con cualquier regularidad impar [20]. Paralelamente a esta línea, en 1900, Petersen incluyó un teorema en uno de sus numerosos artículos [18] en el que se afirma que si un grafo hamiltoniano 4-regular contiene un segundo ciclo, entonces ocurre lo mismo para toda regularidad par >2. Es entonces cuando nos percatamos de la gran trascendencia de la conjetura de Sheehan: Si la conjetura de Sheehan se sostiene, las extensiones de Thomason y Petersen implicarían la inexistencia de grafos hamiltonianos d-regulares únicamente hamiltonianos para 𝑑≥3. 3 EXTENSIÓN DE LA CONJETURA A CUALQUIER REGULARIDAD A lo largo de este capítulo nos centraremos en presentar los resultados para las regularidades pares e impares, que junto a la conjetura de Sheehan, permitirían extender el resultado como se indica en la Conjetura 2.2. 3.1 Caso particular de las regularidades pares. Recordemos que la conjetura de Sheehan describe una característica de los grafos con regularidad 4. En 1891 J. Petersen formuló un lema con el que se puede demostrar que si la conjetura es cierta, también lo es el resultado análogo en cualquier regularidad par [18],[25]. Dicho lema surge como corolario del teorema de los 2-factor de J. Petersen. Teorema 3.1 [Petersen].Sea G un grafo 2k-regular con k un entero positivo; entonces G puede ser expresado como descomposición de 2-factor disjuntos por aristas. Demostración. Nótese que los 2-factor pueden ser vistos como una colección de ciclos disjuntos por aristas tales que juntos tocan cada vértice exactamente una vez. Para probar esta forma generalizada del teorema, Petersen demostró que un grafo 4-regular se puede descomponer en dos 2-factor tomando aristas alternas en un recorrido euleriano. Así, de forma análoga se tiene la descomposición en dos k-factor de cualquier grafo 2𝑘-regular: 16 la conjetura de sheehan en teoría de grafos Sea 𝐺= (𝑉 , 𝐴)un grafo 2𝑘-regular de 𝑛vértices. Podemos asumir sin pérdida de generalidad que 𝐺es conexo, pues en caso contrario bastaría aplicar el mismo razonamiento para cada componente. Como todo vértice de 𝐺tiene grado par, por el Teorema 1.1 existe un circuito euleriano. Sea 𝐶= {𝑣1, 𝑣2, ..., 𝑣1}dicho circuito. Construimos ahora un grafo bipartito 𝐺′[𝐴, 𝐵]con 𝐴= {𝑎1, ..., 𝑎𝑛}y𝐵= {𝑏1, ..., 𝑏𝑛} de modo que 𝑎𝑖y𝑏𝑗son adyacentes en 𝐺′si y sólo si 𝑣𝑖precede inmediatamente a 𝑣𝑗 en 𝐶. Nótese que, construido de este modo, 𝐺′tiene exactamente el doble de vértices que 𝐺pues se tiene que 𝐴=𝐵=𝑉. Ahora bien, cada vértice 𝑣𝑖con 𝑖≠1aparece exactamente 𝑘veces en 𝐶y𝑣1aparece 𝑘+ 1 veces (por aparecer en la primera y última posición). De este modo, cada 𝑣𝑖 precede inmediatamente a otros 𝑘vértices (sabemos que son todos distintos pues en caso contrario encontraríamos más de una vez a la misma arista en 𝐶, lo cual es absurdo por la definición de circuito euleriano) por lo que 𝛿(𝑎𝑖) = 𝑘,∀𝑖= 1, .., 𝑛. Análogamente, cada 𝑣𝑖es inmediatamente posterior a k vértices, por lo que 𝛿(𝑏𝑖) = 𝑘, ∀𝑖= 1, .., 𝑛 también. Se tiene pues que 𝐺′[𝐴, 𝐵]así construido es un grafo bipartito 𝑘-regular. Así, aplicando repetidamente el Corolario 1.1 se consigue una descomposición de 𝐺′ en 1-factor disjuntos (Ver Figura 3.1 situada en la siguiente página). Sea 𝐹un 1-factor de 𝐺′. Como cada arista en 𝐸(𝐺′)viene dada por una arista en 𝐸(𝐶) = 𝐸(𝐺)y viceversa, podemos decir que las aristas de 𝐺′están relacionadas una a una con las de 𝐺. De este modo, cada par de vértices 𝑎𝑖y𝑏𝑖son incidentes a una arista de 𝐹, por lo que cada 𝑣𝑖debe ser incidente a dos aristas del subgrafo de 𝐺correspondiente a 𝐹. Se tiene pues que 𝐹corresponde a un 2-factor en 𝐺, y esto implica que los 1-factor que componen 𝐺′corresponden a una descomposición en 2-factor de 𝐺. □ ⊳Corolario 3.1. Sea G un grafo 2k-regular, con 𝑘≥3, que contiene un ciclo hamiltoniano 𝐶. Supongamos que la conjetura de Sheehan es cierta: todo grafo hamiltoniano 4-regular contiene un segundo ciclo hamiltoniano. Entonces existen al menos dos ciclos hamiltonianos en G. Demostración. Sea 𝑘≥3y𝐺= (𝑉 , 𝐴)un grafo 2k-regular que contiene un ciclo hamiltoniano 𝐶. Como 𝐶es un 2-factor de 𝐺, el grafo 𝐺′= (𝑉 , 𝐴 ∖𝐴(𝐶)) es un grafo (2k-2)-regular. Por tanto, podemos aplicar el Teorema de Petersen (3.1) para encontrar una descomposición de 𝐺′en 2-factor. Sea 𝐹uno de esos 2-factor, se tiene entonces que 𝐹∪𝐶es un grafo 4-regular y por hipótesis ha de contener un segundo ciclo hamiltoniano. Finalmente, como 𝐹∪𝐶 ⊂ 𝐺 se deduce que 𝐺tiene un segundo ciclo hamiltoniano. 3. extensión de la conjetura a cualqier regularidad 17 □ Así, gracias al Teorema de Petersen se deduce que si la conjetura de Sheehan es cierta, entonces todo grafo Hamiltoniano con regularidad par >2 contiene al menos dos ciclos hamiltonianos. Esto, junto con el trabajo de Smith, Tutte y Thomason sobre las regularidades impares implicaría el resultado para grafos hamiltonianos de cualquier regularidad 𝑑≥3. Figura 3.1: Ejemplo de aplicación del Teorema de Petersen para un grafo 6-regular. 18 la conjetura de sheehan en teoría de grafos 3.2 La 3-regularidad y su extensión a toda regularidad impar 3.2.1 Caso particular de la 3-regularidad Treinta años antes de que Sheehan formulara su conjetura, William Tutte publicó lo que podríamos considerar como el primer resultado relacionado con el problema. En el artículo, Tutte atribuye el teorema a Cedric Smith, aunque la primera prueba que consta es la suya publicada en 1946. [24] En lo que sigue, consideraremos 𝐺= (𝑉 , 𝐴)un grafo 3-regular. Para la demostración del resultado necesitaremos las siguientes definiciones: Definición 3.1 [T-coloración].Una T-coloración de un grafo 3-regular G es un conjunto no ordenado de tres clases mutuamente excluyentes de aristas de G , llamadas T-clases, de modo que: a) La unión de todas las clases constituye el total de las aristas de G. b) Cada vértice de 𝐺es incidente con un y sólo un miembro de cada clase. Observación 3.1.La definición anterior es lo que habitualmente llamamos una 3- coloración por aristas, la particularidad está en que al ser un grafo 3-regular todos los vértices tocan los 3 colores. Definición 3.2 [S-subconjunto].Un S-subconjunto de G es la unión de cualquier conjunto de ciclos disjuntos, formados por un número par de aristas de G, de modo que cada vértice de G está contenido en algún ciclo del conjunto. Dado un S-subconjunto 𝑆de 𝐺, el número de componentes de S se denota 𝜎(𝑆) + 1, de modo que 𝜎(𝑆)es un entero no negativo. Observación 3.2.Nótese que como 𝐺es 3-regular, el lema del apretón de manos garantiza que 2|𝐴|= 3|𝑉|, y por tanto 𝐺tiene un número par de vértices. Si contiene un ciclo hamiltoniano 𝐶, es un ciclo con un número par de vértices y por tanto, con un número par de aristas. Es decir, 𝐶es componente de un S-subconjunto. Como contiene todos los vértices de 𝐺ha de ser la única. Así concluimos que los ciclos hamiltonianos de 𝐺son aquellos S-subconjuntos para los cuales 𝜎(𝑆)=0. 3. extensión de la conjetura a cualqier regularidad 19 Sea 𝑆un S-subconjunto y una arista 𝑒∈𝐴definimos el coeficiente: 𝑐𝑒=⎧ ⎪ ⎨ ⎪ ⎩ 1𝑠𝑖 𝑒 ∈𝑆 0𝑠𝑖 𝑒 ∉𝑆 y denotamos por 𝑋(𝑆)a la suma formal de aristas de 𝐺cuyos coeficientes son 𝑐𝑒: 𝑋(𝑆)={∑ 𝑒∈𝐴 𝑐𝑒∗𝑒} Dados 𝑆y𝑆′se define la suma 𝑋(𝑆)+𝑋(𝑆′)coeficiente a coeficiente mod 2. En otras palabras, estamos interpretando 𝑋(𝑆)como un elemento del ℤ∕2-espacio vectorial con base las aristas de 𝐺. Figura 3.2: Ejemplo de una T-coloración. Figura 3.3: Ejemplo de S-subconjuntos en distintos grafos 3-regulares. 26 la conjetura de sheehan en teoría de grafos si ∃𝑆 ⊂ 𝑉 (𝐺)tal que es a la vez rojo-independiente y verde-dominante, se tiene que 𝐺 contiene un segundo ciclo hamiltoniano. Demostración. Consideremos un subgrafo 𝐺′de 𝐺tal que 𝐺′contiene a 𝐶y tal que para cada vértice 𝑤adyacente a un vértice de 𝑆en 𝐶, contiene una única arista verde que lo une con un vértice de 𝑆. Es decir, 𝑉(𝐺′) = 𝑉(𝐺)y𝐸(𝐺′)son todas las aristas de 𝐶más una por cada vértice adyacente a un vértice de 𝑆en 𝐶. De este modo, 𝛿𝐺′(𝑤)=3y para todo 𝑣∈𝐶tal que 𝑣∉𝑆y no sea consecutivo a un vértice de 𝑆en 𝐶se tiene 𝛿𝐺′(𝑣)=2. Nótese que 𝐺′∖𝑆tiene precisamente |𝑆|componentes, cada una de las cuales es un camino cuyos extremos tienen grado impar en 𝐺′y cuyos vértices internos tienen grado 2: Sea 𝑒=𝑥𝑦 con 𝑥∈𝑆. Cada camino hamiltoniano de 𝐺′que empiece con 𝑒debe terminar en un vértice de 𝐺′∖𝑆puesto que debe recorrer los vértices de cada componente consecutivamente; es decir, en dicho ciclo, desde cada vértice de 𝑆pasamos a una componente de 𝐺′∖𝑆, y tras recorrerla por completo, salimos por uno de sus extremos a otro vértice de 𝑆nuevamente. Esto, junto a la condición |𝐺′∖𝑆|=|𝑆|, justifica que el ciclo acabe en un vértice que no pertenece a 𝑆. Ahora, como ese vértice tiene grado impar en 𝐺′, por el argumento del lollipop de Thomason se tiene que 𝐺′tiene un número par de ciclos hamiltonianos que contienen a 𝑒. De aquí se sigue que 𝐺′contiene un ciclo hamiltoniano 𝐶′distinto de 𝐶y por lo tanto 𝐺también. □ Figura 4.1: Ejemplo de conjunto rojo-independiente y verde-dominante (vértices con X) tras colorear un grafo como se indica en el Teorema 4.1. Ilustración representativa de la demostración del teorema. Teorema 4.2. Sea 𝐺un grafo cuyas aristas se han coloreado de rojo y verde. Asumimos que un subgrafo recubridor del subgrafo rojo es r-regular y un subgrafo recubridor 4. prueba para regularidades suficientemente grandes 27 del subgrafo verde es k-regular. Si 𝑟≥3y𝑘 > 200𝑟log 𝑟, entonces 𝐺tiene un conjunto de vértices 𝑆que es rojo-independiente y verde-dominante. Nota 4.1.En el enunciado del teorema anterior, log denota el logaritmo neperiano. Para la prueba del Teorema 4.2 será necesario usar el siguiente lema: Lema 4.1 [Lovász’ Local Lemma [7]].Sean 𝐴1, 𝐴2, ..., 𝐴𝑛sucesos de un espacio probabilístico. Sea 𝐺un grafo con vértices 𝐴1, 𝐴2, ..., 𝐴𝑛tales que para cada 𝑖= 1,2, ..., 𝑛, 𝐴𝑖es un suceso independiente de cualquier combinación de los sucesos adyacentes a él en 𝐺. Supongamos que existen 𝑥1, 𝑥2, ..., 𝑥𝑛números reales positivos menores que 1 tales que para cada 𝑖= 1,2, ..., 𝑛, la probabilidad de 𝐴𝑖satisface ℙ(𝐴𝑖)< 𝑥𝑖∏ 𝑗 (1 − 𝑥𝑗)(4.1) con 𝑗tal que 𝐴𝑗𝐴𝑖∈𝐸(𝐺). Entonces ℙ( 𝐴1∩ 𝐴2∩... ∩ 𝐴𝑛)>0(4.2) Demostración (Teorema 4.2).Sea 𝑝un número real fijo, con 0< 𝑝 < 1. Definimos el espacio probabilístico donde los sucesos son las coloraciones de 𝑉(𝐺) = {𝑣1, 𝑣2, ..., 𝑣𝑚}usando los colores 0 y 1, (de modo que pueden verse como particiones del conjunto de vértices en dos conjuntos, o elecciones de vértices) con la función de probabilidad siguiente: Sea 𝑇una coloración de 𝐺en la cual se selecciona 1 con probabilidad 𝑝y 0 con probabilidad 𝑞. Entonces ℙ(𝑇) = 𝑝𝑞(1 − 𝑝)𝑚−𝑞. Nótese que tras esta definición, a lo largo de la prueba se manejaremos dos coloraciones diferentes: la rojo-verde y la 0-1. El conjunto 𝑆buscado será aquel formado por los vértices coloreados de 1. De este modo, como buscamos que sea rojo-independiente y verde-dominante, deducimos que no puede haber ninguna arista roja cuyos dos extremos sean 1s y además, cualquier vértice que no esté en 𝑆(i.e. con un 0) debe ser adyacente mediante una arista verde al menos a un vértice con un 1. Para cada arista roja 𝑒de 𝐺denotamos por 𝐴𝑒al suceso en el que ambos extremos de 𝑒 tienen el color 1 y los demás vértices tienen un color cualquiera. Por tanto, ℙ(𝐴𝑒) = 𝑝2. De manera similar, para cada vértice 𝑣de 𝐺denotamos por 𝐴𝑣al suceso en el cual 𝑣y sus vértices adyacentes mediante aristas verdes tienen el color 0 y los demás vértices tienen un color cualquiera. Por tanto, ℙ(𝐴𝑣) = (1 − 𝑝)𝑘+1. (Puede consultarse una representación de estos sucesos en la figura incluida más adelante) 28 la conjetura de sheehan en teoría de grafos Se probará la existencia del conjunto 𝑆demostrando que la probabilidad de escogerlo es mayor que 0, o lo que es equivalente, que la probabilidad de que no ocurra ninguno de los sucesos 𝐴𝑒o𝐴𝑣es positiva. Consideremos ahora el grafo 𝐻cuyos vértices son todos los posibles sucesos 𝐴𝑒y𝐴𝑣, de modo que dos vértices son adyacentes en 𝐻si y sólo si los conjuntos de vértices correspondientes en 𝐺intersecan. El grafo 𝐻así definido es como requiere el lema 4.1, nos falta entonces encontrar números reales asociados que permitan satisfacer (4.1). A cada suceso 𝐴𝑒le asociamos 𝑥∈ℝ,0< 𝑥 < 1y a cada suceso 𝐴𝑣le asociamos 𝑦∈ℝ,0<𝑦<1. Sea 𝐴𝑒1un suceso del tipo arista con extremos 𝑣1y𝑣2. 𝐴𝑒1será adyacente a 2(𝑟−1) sucesos 𝐴𝑒𝑖correspondientes a las r-1 aristas rojas incidentes a 𝑣1y a las r-1 incidentes a 𝑣2. Por otra parte, será adyacente a 2(𝑘+ 1) sucesos 𝐴𝑣𝑖: los k correspondientes a las k aristas verdes incidentes a 𝑣1, los k correspondientes a las k incidentes a 𝑣2y a los sucesos 𝐴𝑣1y𝐴𝑣2en sí. Por lo tanto la expresión 4.1 queda de la forma 𝑝2< 𝑥(1 − 𝑥)2𝑟−2(1 − 𝑦)2𝑘+2 (4.3) Mediante un razonamiento análogo para los sucesos del tipo 𝐴𝑣se tiene (1 − 𝑝)𝑘+1 < 𝑦(1 − 𝑥)(𝑘+1)𝑟(1 − 𝑦)𝑘2(4.4) Si las expresiones consideradas se verifican, nos encontramos en las condiciones del lema 4.1. Así, por (4.2) concluiríamos que la probabilidad de que no ocurra ninguno de los sucesos 𝐴𝑒o𝐴𝑣es positiva. Se observa finalmente que eligiendo 𝑝=1 5𝑟,𝑥=1 10𝑟2e𝑦=1 𝑘2,la desigualdad (4.3) se verifica ∀𝑘≥10 y la desigualdad (4.4) se verifica ∀𝑘 > 200𝑟log 𝑟. Se tiene pues que si 𝑟≥3y𝑘 > 200𝑟log 𝑟,∃𝑆∈𝑉(𝐺)rojo-independiente y verde-dominante. □ De este modo, combinando la prueba del Teorema 4.2 con el Teorema 4.1, Thomassen llegó a la siguiente conclusión: Teorema 4.3. Si 𝐺tiene un ciclo hamiltoniano y es m-regular con 𝑚≥300, entonces tiene un segundo ciclo hamiltoniano. 4. prueba para regularidades suficientemente grandes 29 Demostración. Si 𝑟= 2,𝑘= 298 y𝑝, 𝑥, 𝑦 son como en la prueba del Teorema 4.2, entonces (4.3) y (4.4) se satisfacen. □ Así, gracias al Teorema 4.3, Thomassen consiguió probar la cota mencionada al comienzo de la sección y que resulta de gran interés en nuestro estudio: no existen grafos únicamente hamiltonianos r-regulares, con 𝐫≥𝟑𝟎𝟎. 4.2 Mejora de la cota Como se ha mencionado anteriormente, Haxel, Seamone y Verstraete mejoraron el resultado de Thomassen. Para ello se usó nuevamente el método probabilístico. Debido a la extensión de la prueba y la gran cantidad de cálculos de probabilidades, lo que sigue en esta subsección es tan sólo una indicación de la demostración que se puede encontrar con todo detalle en [13]. De nuevo, consideraremos únicamente grafos finitos sin aristas múltiples ni lazos y la siguiente definición: Definición 4.2 [Conjunto dominante independiente de un ciclo 𝐶].Sea 𝐶un ciclo hamiltoniano de un grafo 𝐺. A un conjunto de vértices 𝐼 ⊂ 𝑉 (𝐺)tal que ningún par de vértices de 𝐼es adyacente en 𝐶y cada vértice de 𝐺es adyacente a un vértice de 𝐼en 𝐺∖𝐸(𝐶), se le llama conjunto dominante independiente del ciclo 𝐶. 30 la conjetura de sheehan en teoría de grafos Observación 4.1.Nótese que con esta definición, podemos considerar un caso particular del Teorema 4.1: todo grafo 𝐺que contenga un ciclo hamiltoniano 𝐶tiene al menos dos ciclos hamiltonianos si contiene un conjunto 𝐼dominante independiente de 𝐶. Utilizando lo anterior, indicaremos (siguiendo la estructura del artículo original) la prueba del siguiente teorema. Teorema 4.4. No existen grafos r-regulares únicamente hamiltonianos con 𝑟 > 22, y tampoco grafos r-regulares únicamente hamiltonianos con cintura al menos 7 si 𝑟 > 14. Idea de demostración. Para la demostración del teorema, usaron la versión simétrica del Lema de Lovász: Lema 4.2 [Versión simétrica del Lema de Lovász [7]].Sean 𝐴1, 𝐴2, ..., 𝐴𝑛sucesos en un espacio de probabilidad, y para cada 𝐴𝑖sea 𝐽𝑖⊂{1,2, ..., 𝑛}el conjunto de los valores de 𝑗tales que 𝐴𝑗depende de 𝐴𝑖. Supongamos que existe un número real positivo 0< 𝛾 < 1tal que ℙ(𝐴𝑖)< 𝛾(1 − 𝛾)|𝐽𝑖|(4.5) Entonces se tiene que ℙ( 𝐴1∩ 𝐴2∩... ∩ 𝐴𝑛)≥(1 − 𝛾)𝑛>0(4.6) 4. prueba para regularidades suficientemente grandes 31 PRIMERA PARTE: INTRODUCCIÓN DE LA PRUEBA. Se considera 𝐺un grafo hamiltoniano (d+2)-regular con 𝑛vértices y se escoge por conveniencia 𝑛par, siendo 𝐶= (𝑣1, 𝑣2, ..., 𝑣𝑛, 𝑣1)el ciclo hamiltoniano considerado en 𝐺. Se describe cómo escoger un conjunto 𝐼de manera recursiva, partiendo con 𝐼0=𝑉(𝐶). Para 1≤𝑘≤𝑛 2se define 𝐼𝑘eliminando el vértice 𝑣2𝑘+1 en 𝐼𝑘−1 con probabilidad 𝑝y eliminando ambos vértices 𝑣2𝑘y𝑣2𝑘+2 con probabilidad (1−𝑝). Se tiene además que el conjunto 𝐼=𝐼𝑛 2es independiente en 𝐶y escogemos 𝐼* un conjunto maximal independiente en los vértices de 𝐶que contenga a 𝐼. El objetivo es demostrar que si 𝑑≥22 entonces hay una probabilidad positiva de que 𝐼* sea un conjunto dominante independiente en 𝐶: Para ello de definen los sucesos 𝐴ℎ* y 𝐴ℎen los que un vértice 𝑣ℎ∈𝑉(𝐶)no es dominado por 𝐼* e 𝐼respectivamente. Con estas definiciones, establecen la siguiente propiedad: se tiene que si 𝑣ℎtiene tres vecinos consecutivos en 𝐶entonces es dominado por 𝐼*, luego deducen que basta considerar únicamente los vértices que no cumplen dicha condición. Si se consigue probar que estos vértices son dominados por 𝐼con una probabilidad positiva, entonces 𝐼* será un conjunto dominante independiente de 𝐶y el teorema quedará demostrado. Por el Lema 4.2, esto ocurrirá si existen 𝑝, 𝛾 ∈ (0,1) tal que ∀𝑣ℎque no tenga vecinos consecutivos en 𝐶se tiene ℙ(𝐴ℎ)< 𝛾(1 − 𝛾)𝛿ℎ(4.7) donde 𝛿ℎ=|𝐽ℎ|es el número de sucesos 𝐴𝑗mutuamente dependientes con 𝐴ℎ. SEGUNDA PARTE: ESTIMACIÓN DE ℙ(𝐴ℎ). Para el cálculo de ℙ(𝐴ℎ)se introduce notación necesaria sobre conjuntos relacionados con la vecindad de 𝑣∈𝑉(𝐶)y nuevos sucesos: •Γes la vecindad de 𝑣en 𝐺∖𝐸(𝐶),|Γ|=𝑑. •Un vértice 𝑣𝑖es par o impar si lo es 𝑖respectivamente y un vecino par o impar de 𝑣es un vértice par o impar respectivamente en Γ. •Dado un subconjunto 𝑊 ⊂ 𝑉 se denota al suceso en el que ningún vértice de 𝑊pertenece a 𝐼como [𝑊∩𝐼= ∅]. •𝑄denota a la unión de todos los vértices {𝑣2𝑘−3, 𝑣2𝑘−2, 𝑣2𝑘, 𝑣2𝑘+2, 𝑣2𝑘+3}⊂ Γ,|𝑄|= 5𝑞y𝐴𝑄= [𝑄∩𝐼= ∅]. •𝑅es el conjunto de los vecinos pares de 𝑣en Γ ∖ 𝑄que son adyacentes en 𝐶a un vecino impar de 𝑣y𝐴𝑅= [𝑅∩𝐼= ∅]. 32 la conjetura de sheehan en teoría de grafos •𝑆es el conjunto de los vecinos impares de 𝑣en Γ ∖ 𝑄,|𝑆|=𝑠y𝐴𝑆= [𝑆∩𝐼= ∅]. •𝑇es el conjunto de vecinos pares de 𝑣en Γ ∖ (𝑅∪𝑄),𝑇admite una partición en conjuntos maximales 𝑇1, 𝑇2, ..., 𝑇𝑚y𝐴𝑇= [𝑇∩𝐼= ∅]. •𝑆𝑖es el conjunto de vértices impares adyacentes en 𝐶a un vértice de 𝑇𝑖, 𝑡𝑖=|𝑆𝑖|y𝑡= 𝑚 ∑ 𝑖=1 𝑡𝑖. •𝜌es el número de conjuntos de la forma {𝑣2𝑘, 𝑣2𝑘+1, 𝑣2𝑘+2} que contienen un vértice en 𝑅y ninguno en 𝑆. Con estas definiciones, se llaga a una primera aproximación ℙ(𝐴ℎ) = ℙ(𝐴𝑄∩𝐴𝑅∩𝐴𝑆∩𝐴𝑇) = 𝑝2𝑞(1 − 𝑝)2𝑞(1 − 𝑝)𝜌𝑝𝑠ℙ(𝐴𝑇|𝐴𝑅)(4.8) Usando un lema auxiliar se deduce que ℙ(𝐴𝑇|𝐴𝑅) = 𝑚 ∏ 𝑖=1 (1 − 𝑝)𝑡𝑖Φ(𝑡𝑖+ 1) (4.9) donde Φ(𝑛) = 𝛽+2 2𝛽+2 (𝛽+2 2)𝑛+𝛽 2𝛽+2 (1 − 𝛽+2 2)𝑛,𝛽=√1+4𝛼− 1 y𝛼=𝑝 1−𝑝. Finalmente, para aplicar el lema 4.2 se utilizan también resultados auxiliares y se llega a ℙ(𝐴ℎ)≤(1 − 𝑝)𝑑+1𝜑(𝑑+ 2) (4.10) donde 𝜑(𝑛) = 𝛽+2 2𝛽+2 (𝛽+2 2)𝑛+𝛽 2𝛽+2 |1 − 𝛽+2 2|𝑛. TERCERA PARTE: DEDUCCIÓN DE LOS RESULTADOS •PRIMER RESULTADO: Como vimos en la sección 3.2.2, por Thomason se tiene que todo grafo hamiltoniano r-regular con 𝑟impar tiene al menos dos ciclos hamiltonianos. Consideremos pues 𝐻un grafo hamiltoniano r-regular con 𝑟≥24 par. Si 𝐶es un ciclo hamiltoniano entonces 𝐻∖𝐸(𝐶)es un grafo (r-2)-regular, y por el Teorema de Petersen 3.1 contiene un 2-factor. Así, si eliminamos este 2-factor de 𝐻se obtiene un grafo (r-2)-regular que contiene al ciclo hamiltoniano 𝐶. Repitiendo este procedimiento, llegamos a un grafo hamiltoniano 24-regular, 𝐺, que contiene a 𝐶. Finalmente, tomando 𝑑= 22 y aplicando el razonamiento descrito se tiene que para 4. prueba para regularidades suficientemente grandes 33 𝑝= 33∕50 y𝛾= 1∕25, existe una probabilidad positiva de que 𝐼sea un conjunto independiente dominante de 𝐶. De este modo, 𝐺contiene un conjunto independiente dominante 𝐼* de 𝐶y por lo tanto 𝐻tiene al menos dos ciclos hamiltonianos distintos. Esto prueba la primera afirmación del teorema. •SEGUNDO RESULTADO: Sea 𝐺un grafo r-regular de cintura al menos 7, donde 𝑟=𝑑+ 2, y sea 𝐶un ciclo hamiltoniano en 𝐺. Como en la primera parte, por el Teorema 3.1 basta considerar el caso 𝑑= 14. Para un vértice 𝑣ℎ∈𝑉(𝐶)se define el suceso 𝐴∗ ℎ="𝑣ℎno es dominado por 𝐼*". Se escoge 𝑝= 0.657 y se tiene ℙ[𝑤∉𝐼∗]=2𝑝2−𝑝3si 𝑤es impar y ℙ[𝑤∉𝐼∗] = 1 − 𝑝2si 𝑤es par. Por la definición de 𝐼* se tiene: ℙ[𝐴∗ ℎ] = (2𝑝2−𝑝3)𝑠(1 − 𝑝2)𝑑−𝑠+1 donde 𝑠es el número de vecinos impares de 𝑣ℎen 𝐺∖𝐸(𝐶)(incluido él mismo si ℎes impar). Sea 𝛿ℎel número de eventos 𝐴∗ 𝑗que son mutuamente dependientes con 𝐴∗ ℎ. Como 𝐺tiene cintura al menos 7, los sucesos 𝑥∈𝐼* e𝑦∈𝐼* serán independientes mientras la distancia entre ellos en 𝐶sea mayor que 3. Se comprueba entonces que 𝛿ℎ≤5𝑑2+ 8𝑑+ 4 + 2(𝑑+ 1)𝑠 Finalmente, mediante algunos cálculos se deduce que si 𝛾=1 20 y𝑑= 14, entonces ℙ[𝐴∗ ℎ]< 𝛾(1 − 𝛾)𝛿ℎy por el teorema 4.2 se tiene que con probabilidad positiva 𝐼* es un conjunto dominante independiente de 𝐶 en 𝐺. □ Resumidamente, podemos interpretar de todo lo anterior que Haxel, Seamone y Verstraete aplicaron el método probabilístico en grafos (𝑑+2)-regulares definiendo nuevos sucesos, y mediante cálculos con sus probabilidades obtuvieron una condición para que la probabilidad de que existiera el conjunto dominante independiente fuera positiva. Con ello discutieron el valor de esos parámetros en función de la regularidad interesada, obteniendo finalmente unas cotas más finas que Thomassen. 5 GRAFOS BIRREGULARES DE REGULARIDAD 4 Y 14 Uno de los resultados más recientes que relacionan el número de ciclos hamiltonianos y la regularidad en grafos se debe al matemático Herbert Fleischner. En 2013 publicó un artículo [8] en el cual demuestra el siguiente teorema: Teorema 5.1. Existe una familia infinita de grafos únicamente hamiltonianos cuyo grado mínimo es 4 y máximo arbitrario. También existen infinitos grafos únicamente hamiltonianos con birregularidad 4 y 14. Sin embargo, a pesar de que todos estos grafos tienen vértices con valencia 4, no son regulares, por lo que la conjetura de Sheehan sigue sin resolverse. Por tanto, el objetivo de esta construcción es minimizar el número de vértices con grado distinto a 4 y acercarnos así a las condiciones de la conjetura de Sheehan. Para la construcción se necesita definir la siguiente operación: Definición 5.1 [Operación de empalme].Sean 𝐺y𝐻grafos. Supongamos que 𝐺 tiene un vértice 𝑥∈𝑉(𝐺)tal que 𝛿(𝑥)=3y denotemos a sus vecinos por 𝑁(𝑥) = {𝑦, 𝑢, 𝑣}. Sean 𝑦, 𝑢1, 𝑣1∈𝑉(𝐻), y sea 𝛾 𝑒 =𝑒 si 𝑒 =𝑢1𝑣1∈𝐸(𝐻)y𝛾 𝑒 = ∅ en otro caso. Al grafo que se obtiene al considerar (𝐺∖𝑥)∪(𝐻∖𝛾 𝑒)∪{𝑢𝑢1, 𝑣𝑣1} mediante la identificación 𝑦=𝑦, se le llama H-empalme de 𝐺en 𝑥respecto a 𝑒=𝑥𝑦 y se denota 𝐺<𝐻>. (Ver figura en la siguiente página) Nota 5.1.En la construcción de los grafos únicamente hamiltonianos consideraremos también grafos 𝐺con un único camino hamiltoniano que une a 𝑥, 𝑦 ∈𝑉(𝐺). Para facilitar la escritura, a lo largo de toda la sección diferenciaremos a los primeros de los 42 la conjetura de sheehan en teoría de grafos Figura 5.8: Grafo 𝐹con semiaristas incidentes a 𝑢1y𝑣1para una posterior construcción. Se tiene 𝛿(𝑧𝑖) = 14,1≤𝑖≤5y𝛿(𝑧)=4. Finalmente, se lleva a cabo una construcción análoga a la anterior para 𝑈∗, tomando dos copias 𝐹∗y𝐹∗∗ que generará un grafo UH: 𝑈=𝐹∗∪𝐹∗∗ ∪ {𝑢∗ 1𝑢∗∗ 1, 𝑣∗ 1𝑣∗∗ 1} o bien 𝑈=𝐹∗∪𝐹∗∗ ∪ {𝑢∗ 1𝑣∗∗ 1, 𝑣∗ 1𝑢∗∗ 1}. En cualquier caso, el grafo 𝑈es birregular con valencias 4 y 14, por lo que además es euleriano. (ver 1.1). Además, como ((15𝑥5 + 3 + 2)𝑥2 − 1)𝑥2 = 338, el grafo tiene 338 vértices, de los cuales sólo 20 tienen grado 14. Este nuevo grafo UH puede ser usado para la operación de empalme descrita con el objetivo de crear un grafo UH más grande. De este modo obtenemos una familia infinita de grafos UH con vértices de grado 4 y cuyo grado máximo crecerá tanto como nuevos grafos UH construyamos con este procedimiento. Podemos hacerlo tomando 𝑉′=𝑉(𝐻)al definir 𝐻[𝑉′, 𝑧]y repetirlo en cada nuevo grafo UH construido, aumentando así el grado máximo en cada iteración. 5. grafos birregulares de regularidad 4 y 14 43 Por otra parte, si queremos que el grado máximo sea lo más pequeño posible, podemos generar la familia infinita tomando dos copias 𝑈∗y𝑈∗∗ del grafo 𝑈y realizar la última construcción con estas copias en lugar de las de 𝐹. Reiterando una y otra vez se tiene una familia infinita de grafos UH cuyos vértices son de grado 4 y 14 únicamente. □ 6 OTROS RESULTADOS RELACIONADOS CON LA CONJETURA DE SHEEHAN En este último capítulo, repasamos brevemente diferentes trabajos relacionados en mayor o menor grado con la conjetura de Sheehan. Los resultados que se presentan en ellos han surgido en el contexto de la investigación sobre grafos únicamente hamiltonianos. 6.1 Grafos hamiltonianos y grado 3 En [6], R.C. Entringer y H. Swart, motivados por el hecho de que todo grafo hamiltoniano 3-regular debiera contener al menos 3 ciclos hamiltonianos, se preguntaron si ocurría lo mismo para grafos hamiltonianos con grado mínimo 3. En el artículo, responden de manera negativa a esta pregunta, mostrando grafos con 𝑛= 2𝑚+ 1, 𝑚≥5, vértices en los cuales un vértice tiene grado 4, todos los demás tienen grado 3, y solo existen dos ciclos hamiltonianos. Aunque estos grafos construidos por Entringer y Swart contienen un único ciclo hamiltoniano, contienen otros ciclos que casi recubren todos los vértices del grafo, por lo que es natural preguntarse si esta situación es del todo inevitable. En este contexto se tiene la siguiente recomendación. 46 la conjetura de sheehan en teoría de grafos 6.2 Aproximación asintótica a la conjetura de Sheehan En 2017, A. Girão, T. Kittipassorn y B. Narayanan publican un artículo [9], en el que se prueba que si un grafo de 𝑛vértices con grado mínimo al menos 3 contiene un ciclo hamiltoniano, entonces contiene otro ciclo de longitud 𝑛−𝑜(𝑛); (más precisamente, de longitud 𝑛−𝑐𝑛4 5con 𝑐 > 0constante). Para ello combinan métodos constructivos, técnicas basadas en conjuntos parcialmente ordenados y argumentos no constructivos basados en la paridad. Este artículo resulta de gran interés pues supone que la conjetura de Sheehan se verifica asintóticamente. 6.3 Ejemplos de grafos 3-conexos únicamente hamiltonianos En 1986, E. Grinberg encontró algunos grafos únicamente hamiltonianos 3-conexos no planares. Estos resultados fueron recopilados por D. Zeps a partir de varios fragmentos de sus manuscritos, y recogidos en la memoria [10], donde afirma que ya los había encontrado en 1978. 6.4 Bondy-Jackson Como consecuencia de lo anterior J.A. Bondy [3] planteó una nueva pregunta en esta línea: ¿existen grafos únicamente hamiltonianos de grado mínimo al menos 4? Junto con B. Jackson, Bondy demostró en [2] que un grafo únicamente hamiltoniano tiene un vértice de grado ≤𝑐log28𝑛+ 3, donde 𝑐= (2 − log23)−1 ≈ 2.41. Este resultado se mejoró en [13], y posteriormente se obtuvo una estimación aún mejor en [1]. Bondy y Jackson [2] también muestran que un grafo UH planar contiene un vértice de grado 2 o 3, y conjeturan que los grafos UH planares siempre tienen al menos dos vértices de grado 2: En el contexto de esta nueva conjetura, recordemos que un grafo es outerplanar si admite una representación plana con todos sus vértices en la cara exterior del dibujo. En relación con estos grafos, dado que todo grafo 2-conexo de este tipo tiene al menos 6. otros resultados relacionados con la conjetura de sheehan 47 dos vértices de grado 2 y es únicamente hamiltoniano, la conjetura se cumple para este caso particular. 6.5 Grafos bipartitos En el artículo [21], Thomassen expone varios resultados como consecuencia del estudio de la coloración de grafos bipartitos: Prueba que un grafo bipartito únicamente hamiltoniano tiene un vértice de grado 2 en cada clase de color y que debido a ello, todo grafo bipartito hamiltoniano de grado mínimo 𝑑tiene al menos 21−𝑑𝑑!ciclos hamiltonianos. También concluye que todo grafo bipartito hamiltoniano de grado mínimo al menos 4 y cintura 𝑔tiene al menos (3 2)𝑔 8ciclos hamiltonianos e indica cómo la existencia de más de un ciclo hamiltoniano puede llevar a un método general de reducción para grafos hamiltonianos. 6.6 Otros grafos únicamente hamiltonianos En algunos artículos, (véanse [15],[14],[16]) se han estudiado grafos únicamente hamiltoniano-conexos desde un vértice. Además, en 1981, L.S. Melnikov [17], se pregunta si existen triangulaciones (simples) del plano que son grafos UH. Esta pregunta tiene una respuesta negativa por los resultados de [11],[17]. Bibliografía [1] Abbasi, S., and Jamshed, A. A degree constraint for uniquely hamiltonian graphs. Graphs and Combinatorics 22, 4 (Dec 2006), 433–442. [2] Bondy, J., and Jackson, B. Vertices of small degree in uniquely hamiltonian graphs. Journal of Combinatorial Theory, Series B 74, 2 (1998), 265–275. [3] Bondy, J. A. Basic Graph Theory: Paths and Circuits. MIT Press, Cambridge, MA, USA, 1996, p. 3–110. [4] Bondy, J. A., and Murty, U. S. R. Graph Theory with Applications. Elsevier, New York, 1976. [5] Broersma, H. On some intriguing problems in hamiltonian graph theory—a survey. Discrete Mathematics 251, 1 (2002), 47–69. Cycles and Colourings. [6] Entringer, R., and Swart, H. Spanning cycles of nearly cubic graphs. Journal of Combinatorial Theory, Series B 29, 3 (1980), 303–309. [7] Erdős, P., and László, L. Problems and results on 3-chromatic hypergraphs and some related questions. Coll Math Soc J Bolyai 10 (01 1974). [8] Fleischner, H. Uniquely hamiltonian graphs of minimum degree 4. J. Graph Theory 75, 2 (2013), 167–177. [9] Girão, A., Kittipassorn, T., and Narayanan, B. Long cycles in hamiltonian graphs. Israel Journal of Mathematics 229, 1 (Jan 2019), 269–285. [10] Grinberg, E., and Zeps, D. Three-connected graphs with only one hamiltonian circuit. Article compiled from several fragments from Grinbergs manuscripts by D. Zeps (1986). 50 la conjetura de sheehan en teoría de grafos [11] Hakimi, S. L., Schmeichel, E. F., and Thomassen, C. On the number of hamiltonian cycles in a maximal planar graph. Journal of Graph Theory 3, 4 (1979), 365–370. [12] Hall, P. On representatives of subsets. Journal of The London Mathematical Society-second Series (1935), 26–30. [13] Haxell, P., Seamone, B., and Verstraete, J. Independent dominating sets and hamiltonian cycles. Journal of Graph Theory 54, 3 (2007), 233–244. [14] Hendry, G. The size of graphs uniquely hamiltonian-connected from a vertex. Discrete Mathematics 61, 1 (1986), 57–60. [15] Hendry, G. R., Knickerbocker, C., Lock, P. F., and Sheard, M. Forbidden subgraphs of graphs uniquely hamiltonian-connected from a vertex. Discrete Mathematics 187, 1 (1998), 281–290. [16] Knickerbocker, C., Lock, P. F., and Sheard, M. On the structure of graphs uniquely hamiltonian-connected from a vertex. Discrete Mathematics 88, 1 (1991), 33–48. [17] Kratochvíl, J., and Zeps, D. On the number of hamiltonian cycles in triangulations. J. Graph Theory, 12(2) (1998), 191–194. [18] Petersen, J. Die Theorie der regulären graphs. Acta Mathematica 15, none (1900), 193 – 220. [19] Sheehan, J. The multiplicity of hamiltonian circuits in a graph, in: Recent advances in graph theory. M. Fiedler, pp. 447–480. [20] Thomason, A. G. Hamiltonian cycles and uniquely edge colourable graphs. Annals of discrete mathematics 3 (1978), 259–268. [21] Thomassen, C. On the number of hamiltonian cycles in bipartite graphs. Combinatorics, Probability and Computing 5, 4 (1996), 437–442. [22] Thomassen, C. Chords of longest cycles in cubic graphs. Journal of Combinatorial Theory, Series B 71, 2 (1997), 211–214. [23] Thomassen, C. Independent dominating sets and a second hamiltonian cycle in regular graphs. Journal of Combinatorial Theory, Series B 72, 1 (1998), 104–109. BIBLIOGRAFÍA 51 [24] Tutte, W. T. On hamiltonian circuits. Journal of The London Mathematical Society-second Series (1946), 98–101. [25] Wagner, A. On the existence of a second hamilton cycle in hamiltonian graphs with symmetry.