En la 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 enteros entre 0 y m inclusive, de modo que no hay dos vértices que compartan una etiqueta y cada arista se identifica de forma única por la diferencia absoluta entre sus extremos, de modo que esta magnitud se encuentre entre 1 y m inclusive. [1] Un gráfico que admite un etiquetado elegante se denomina 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 , que lleva el nombre de Gerhard Ringel y Anton Kotzig , ya veces abreviada como GTC . [3] Plantea la hipótesis de que todos los árboles son elegantes. Todavía es una conjetura abierta, aunque una conjetura relacionada pero ligeramente más débil conocida como conjetura de Ringel se demostró cierta en 2020. [4] [5] [6] La conjetura de Ringel-Kotzig también se conoce como la "conjetura de etiquetado elegante". Kotzig una vez llamó al esfuerzo por probar 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 números enteros entre 0 y m + 1 inclusive, de modo que no hay dos vértices que compartan una etiqueta, y cada borde se identifica de forma única por el diferencia absoluta entre sus puntos finales, de manera que esta magnitud se encuentra entre 1 y m + 1 inclusive.
Otra conjetura en la teoría de grafos es la Conjetura de Rosa , llamada así por Alexander Rosa , que dice que todos los cactus triangulares son agraciados o casi agraciados. [8]
Un gráfico agraciado con bordes 0 a m se conjetura que no tiene menos devértices, debido a la escasez de resultados de la regla . Esta conjetura se ha verificado para todos los gráficos con 213 aristas o menos.
Resultados seleccionados
- En su papel original, Rosa demostró que un gráfico euleriano con número de aristas m ≡ 1 (mod 4) o m ≡ 2 (mod 4) no puede ser agraciado. [2]
- También en su papel original, Rosa demostró que el ciclo C n es agraciado si y sólo si n ≡ 0 (mod 4) o n ≡ 3 (mod 4).
- Todos los gráficos de ruta y los gráficos de oruga son elegantes.
- Todos los gráficos de langosta con una combinación perfecta son elegantes. [9]
- Todos los árboles con un máximo de 27 vértices son elegantes; este resultado fue mostrado por Aldred y McKay en 1998 usando 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 Graceful Tree Verification Project, un proyecto de computación distribuida dirigido por Wenjie Fang. [13]
- Todos los gráficos de ruedas , gráficos web, gráficos de timón , gráficos de engranajes y cuadrículas rectangulares son elegantes. [10]
- Todos los hipercubos n- dimensionales son elegantes. [14]
- Todos los gráficos simples con cuatro o menos vértices son elegantes. Los únicos gráficos simples sin gracia con cinco vértices son el ciclo de 5 ( pentágono ); el gráfico completo K 5 ; y el gráfico de mariposas . [15]
Ver también
- Etiquetado elegante en los bordes
- Lista de conjeturas
Referencias
- ^ Virginia Vassilevska , "Codificación y etiquetado elegante de árboles". SURF 2001. PostScript
- ↑ a b Rosa, A. (1967), "Sobre ciertas valoraciones de los vértices de un gráfico", Teoría de los gráficos (Simposios internacionales, Roma, 1966) , Nueva York: Gordon y Breach, págs. 349–355, Señor 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 etiquetado de árboles", Utilitas Mathematica , 21 : 31–48, MR 0668845.
- ^ Hartnett, Kevin. "Rainbow Proof 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 etiquetado de árboles", Utilitas Mathematica , 21 : 31–48, MR 0668845.
- ^ Rosa, A. (1988), "Cyclic Steiner Triple Systems and Labelings of Triangular Cacti", 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.
- ^ a b 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 la 18ª ed.) (Electrónico), MR 1668059.
- ^ Aldred, REL; McKay, Brendan D. (1998), "Etiquetado de árboles agraciado y armonioso", 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 Computacional Aproximación al árbol agraciado conjetura , arXiv : 1003.3045 , bibcode : 2010arXiv1003.3045F. Véase también Proyecto Graceful Tree Verification
- ^ Kotzig, Anton (1981), "Descomposiciones de gráficos completos en cubos isomórficos", Journal of Combinatorial Theory, Serie B , 31 (3): 292-296, doi : 10.1016 / 0095-8956 (81) 90031-9 , MR 0638285.
- ^ Weisstein, Eric W. "Gráfica elegante" . MathWorld .
enlaces externos
- Video de numberphile sobre la conjetura del árbol elegante
Otras lecturas
- (K. Eshghi) Introducción a gráficos agraciados , Universidad de Tecnología de Sharif, 2002.
- (ONU Deshmukh y Vasanti N. Bhat-Nayak), Nuevas familias de elegantes árboles de plátano - Proceedings Mathematical Sciences, 1996 - Springer
- (M. Haviar, M. Ivaska), Etiquetado de vértices de gráficos simples, Investigación y exposición en matemáticas, Volumen 34, 2015.
- ( Ping Zhang ), Una vista caleidoscópica de los colores de los gráficos, SpringerBriefs in Mathematics, 2016 - Springer