Un etiquetado elegante. Las etiquetas de los vértices están en negro y las etiquetas de los bordes, en rojo.
En teoría de grafos , un etiquetado elegante de un gráfico con m aristas es un etiquetado de sus vértices con algún subconjunto de números enteros de 0 a m inclusive, de modo que no haya dos vértices que compartan una etiqueta y cada arista se identifique de forma única mediante la diferencia absoluta. entre sus puntos finales, de modo que esta magnitud se encuentre entre 1 y m inclusive. [1] Un gráfico que admite un etiquetado elegante se llama gráfico elegante .
El nombre "etiquetado elegante" se debe a Solomon W. Golomb ; Este tipo de etiquetado recibió originalmente el nombre de etiquetado β por Alexander Rosa en un artículo de 1967 sobre etiquetado de gráficos. [2]
Una conjetura importante en la teoría de grafos es la conjetura del árbol elegante o conjetura de Ringel-Kotzig , llamada así en honor a Gerhard Ringel y Anton Kotzig , y a veces abreviada GTC . [3]
Se plantea la hipótesis de que todos los árboles son elegantes. Todavía es una conjetura abierta, aunque en 2020 se demostró parcialmente una conjetura relacionada pero más débil conocida como "conjetura de Ringel". [4] [5] [6]
Kotzig una vez llamó al esfuerzo por probar la conjetura una "enfermedad". [7]
Otra versión más débil del etiquetado elegante es el etiquetado casi elegante , en el que los vértices se pueden etiquetar utilizando algún subconjunto de números enteros en [0, m + 1] de modo que no haya dos vértices que compartan una etiqueta y cada borde se identifique de forma única mediante el diferencia absoluta entre sus puntos finales (esta magnitud se encuentra en [1, m + 1] ).
Otra conjetura de la teoría de grafos es la conjetura de Rosa , que lleva el nombre de Alexander Rosa, que dice que todos los cactus triangulares son gráciles o casi gráciles. [8]
Se conjetura que un gráfico elegante con aristas de 0 a m tiene no menos de vértices, debido a los escasos resultados de la regla. Esta conjetura se ha verificado para todos los gráficos con 213 aristas o menos.
Un gráfico elegante con 27 aristas y 9 vértices.
Resultados seleccionados
En su artículo original, Rosa demostró que un gráfico euleriano con un número de aristas m ≡ 1 (mod 4) o m ≡ 2 (mod 4) no puede ser elegante. [2]
También en su artículo original, Rosa demostró que el ciclo C n es grácil si y sólo si n ≡ 0 (mod 4) o n ≡ 3 (mod 4).
Todos los árboles con como máximo 27 vértices son elegantes; este resultado fue demostrado por Aldred y McKay en 1998 utilizando un programa informático. [10] [11] Esto se extendió a árboles con como máximo 29 vértices en la tesis de honores de Michael Horton. [12] Otra extensión de este resultado hasta árboles con 35 vértices fue reclamada en 2010 por el Graceful Tree Verification Project, un proyecto de computación distribuida dirigido por Wenjie Fang. [13]
^ Virginia Vassilevska , "Codificación y etiquetado elegante de árboles". SURF 2001. Posdata
^ abc Rosa, A. (1967), "Sobre ciertas valoraciones de los vértices de un gráfico", Teoría de los grafos (Internat. Sympos., Roma, 1966) , Nueva York: Gordon y Breach, págs. 349–355, MR 0223271.
^ Wang, Tao-Ming; Yang, Cheng-Chang; Hsu, Lih-Hsing; Cheng, Eddie (2015), "Infinitas versiones equivalentes de la conjetura del árbol elegante", Análisis aplicable y matemáticas discretas , 9 (1): 1–12, doi : 10.2298/AADM141009017W , MR 3362693
^ Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2020). "Una prueba de la conjetura de Ringel". arXiv : 2001.02665 [math.CO].
^ Huang, C.; Kotzig, A .; Rosa, A. (1982), "Más resultados sobre el etiquetado de árboles", Utilitas Mathematica , 21 : 31–48, MR 0668845.
^ Hartnett, Kevin. "La prueba del arco iris muestra que los gráficos tienen partes uniformes". Revista Quanta . Consultado el 29 de febrero de 2020 .
^ Huang, C.; Kotzig, A .; Rosa, A. (1982), "Más resultados sobre el etiquetado de árboles", Utilitas Mathematica , 21 : 31–48, MR 0668845.
^ Rosa, A. (1988), "Sistemas triples cíclicos de Steiner y etiquetado de cactus triangulares", Scientia , 1 : 87–95.
^ Morgan, David (2008), "Todas las langostas con combinaciones perfectas son elegantes", Boletín del Instituto de Combinatoria y sus Aplicaciones , 53 : 82–85, hdl :10402/era.26923.
^ ab Gallian, Joseph A. (1998), "Un estudio dinámico del etiquetado de gráficos", Electronic Journal of Combinatorics , 5 : Dynamic Survey 6, 43 págs. (389 págs. en 18.ª ed.) (electrónico), MR 1668059.
^ Aldred, REL; McKay, Brendan D. (1998), "Etiquetados de árboles elegantes y armoniosos", Boletín del Instituto de Combinatoria y sus Aplicaciones , 23 : 69–72, MR 1621760.
^ Horton, Michael P. (2003), Árboles agraciados: estadísticas y algoritmos.
^ Fang, Wenjie (2010), Un enfoque computacional de la conjetura del árbol agraciado , arXiv : 1003.3045 , Bibcode :2010arXiv1003.3045F. Véase también Proyecto de verificación de árboles agraciados
^ Kotzig, Anton (1981), "Descomposiciones de gráficas completas en cubos isomórficos", Journal of Combinatorial Theory, Serie B , 31 (3): 292–296, doi : 10.1016/0095-8956(81)90031-9 , SEÑOR 0638285.
