Un etiquetado elegante. Las etiquetas de los vértices están en negro y las de los bordes en rojo.
En teoría de grafos , un etiquetado elegante de un grafo con m aristas es un etiquetado de sus vértices con algún subconjunto de los números enteros de 0 a m inclusive, de modo que ningún par de vértices comparta una etiqueta, y cada arista se identifica de forma única por la diferencia absoluta entre sus puntos finales, de modo que esta magnitud se encuentra entre 1 y m inclusive. [1] Un grafo que admite un etiquetado elegante se denomina grafo elegante .
El nombre de "etiquetado elegante" se debe a Solomon W. Golomb ; este tipo de etiquetado recibió originalmente el nombre de etiquetado β por parte de Alexander Rosa en un artículo de 1967 sobre etiquetado de gráficos. [2]
Un importante problema abierto en la teoría de grafos es la conjetura del árbol elegante o conjetura de Ringel-Kotzig , llamada así por Gerhard Ringel y Anton Kotzig , y a veces abreviada GTC (que no debe confundirse con la conjetura de Kotzig sobre grafos regularmente conexos por caminos). [3]
Esta hipótesis sostiene que todos los árboles son elegantes. Sigue siendo 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 calificó el esfuerzo por demostrar la conjetura como 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 los números enteros en [0, m + 1] de modo que ningún par de vértices comparta una etiqueta, y cada borde se identifica de forma única por la diferencia absoluta entre sus puntos finales (esta magnitud se encuentra en [1, m + 1] ).
Otra conjetura en la teoría de grafos es la conjetura de Rosa , llamada así en honor a Alexander Rosa, que dice que todos los cactus triangulares son gráciles o casi gráciles. [8]
Se supone que un grafo elegante con aristas de 0 a m no tiene menos de vértices, debido a los resultados de la regla dispersa . Esta conjetura se ha verificado para todos los grafos 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 elegante si y sólo si n ≡ 0 (mod 4) o n ≡ 3 (mod 4).
Todos los árboles con un máximo de 27 vértices son elegantes; este resultado fue demostrado por Aldred y McKay en 1998 utilizando un programa de computadora. [10] [11] Esto se extendió a árboles con un máximo de 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 Proyecto de Verificación de Árboles Elegantes, un proyecto de computación distribuida dirigido por Wenjie Fang. [13]
^ Virginia Vassilevska , "Codificación y etiquetado elegante de árboles". SURF 2001. PostScript
^ abc Rosa, A. (1967), "Sobre ciertas valoraciones de los vértices de un grafo", Teoría de grafos (Simposios internacionales, 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), "Resultados adicionales 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), "Resultados adicionales sobre el etiquetado de árboles", Utilitas Mathematica , 21 : 31–48, MR 0668845.
^ Rosa, A. (1988), "Sistemas triples cíclicos de Steiner y etiquetados de cactus triangulares", Scientia , 1 : 87–95.
^ Morgan, David (2008), "Todas las langostas con emparejamientos perfectos 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 pp. (389 pp. en la 18.ª ed.) (electrónico), MR 1668059.
^ Aldred, REL; McKay, Brendan D. (1998), "Etiquetas elegantes y armoniosas de árboles", Boletín del Instituto de Combinatoria y sus Aplicaciones , 23 : 69–72, MR 1621760.
^ Horton, Michael P. (2003), Árboles elegantes: estadísticas y algoritmos.
^ Fang, Wenjie (2010), Un enfoque computacional para la conjetura del árbol elegante , arXiv : 1003.3045 , Bibcode :2010arXiv1003.3045FVéase también Proyecto de verificación de árboles elegantes
^ Kotzig, Anton (1981), "Descomposiciones de gráficos completos en cubos isomorfos", Journal of Combinatorial Theory, Serie B , 31 (3): 292–296, doi : 10.1016/0095-8956(81)90031-9 , MR 0638285.
