Marcado elegante

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de febrero de 2021; las comprobaciones requieren 3 ediciones .

El etiquetado elegante en la teoría de grafos es tal etiquetado de vértice de un gráfico con bordes por algún subconjunto de números enteros entre 0 e inclusive que los diferentes vértices se etiquetan con números diferentes, y tal que si cada borde está etiquetado por la diferencia absoluta de las etiquetas de los vértices que conecta, entonces todas las diferencias resultantes serán diferentes [1] . Un gráfico que permite un etiquetado elegante se llama gráfico elegante .

El autor del término "marcado elegante" es Solomon Golomb ; Alexander Rosa fue el primero en destacar esta clase de etiquetado y presentarla bajo el nombre -markup en un artículo de 1967 sobre etiquetado de gráficos .  [2] .

Una de las principales hipótesis no probadas en la teoría de grafos es la conjetura del árbol  agraciado , también conocida como la conjetura de Ringel- Kotzig en honor a Gerhard Ringel y Anton Kotzig , quienes la formularon y afirman que todos los árboles son agraciados. A partir de 2017, la conjetura aún no está probada, pero debido a la simplicidad de la formulación, atrajo la atención de los amantes de las matemáticas (como resultado de lo cual aparecieron muchas pruebas incorrectas), Kotzig en un momento incluso describió intentos masivos para demostrarlo como una “enfermedad” [3] .  

Principales resultados

En el artículo original, Rosa demostró que un gráfico de Euler con aristas m ≡ 1 (mod 4) o m ≡ 2 (mod 4) no puede ser elegante. [2] , también muestra que el ciclo C n es elegante si y solo si n ≡ 0 (mod 4) o n ≡ 3 (mod 4).

Graciosos son todos los caminos , las orugas , todas las langostas con una combinación perfecta [4] , todas las ruedas , redes , timones , engranajes , todas las celosías rectangulares [5] , así como todos los hipercubos n -dimensionales [ 6] . Todos los gráficos simples con 4 o menos vértices son elegantes, los únicos gráficos simples no elegantes en cinco vértices son el ciclo 5 ( pentágono ) , el gráfico K 5 completo y la mariposa [7] .

Todos los árboles con no más de 27 vértices son elegantes; este resultado fue obtenido por Aldred y McKay en 1998 usando un programa de computadora [  5] [8] ; La mejora de su enfoque (utilizando un método computacional diferente) hizo posible mostrar en 2010 que todos los árboles de hasta 35 vértices inclusive son elegantes; este es el resultado del Proyecto de verificación de árboles elegantes dirigido por Wenjie Fang [9] .

Notas

  1. ↑ Virginia Vassilevska, "Codificación y elegante etiquetado de árboles". SURF 2001. PostScript Archivado el 25 de septiembre de 2006 en Wayback Machine .
  2. ↑ 1 2 Rosa, A. Theory of Graphs (Internat. Sympos., Rome, 1966)  (sin especificar) . - Nueva York: Gordon and Breach, 1967. - S. 349-355 .
  3. ↑ Huang, C.; Kotzig, A.; Rosa, A. Resultados adicionales sobre etiquetado de árboles  (indefinidos)  // Utilitas Mathematica. - 1982. - T. 21 . - S. 31-48 .
  4. ↑ Morgan, David. Todas las langostas con combinaciones perfectas son elegantes  //  Boletín del Instituto de Combinatoria y sus Aplicaciones. - 2008. - T. 53 . - S. 82-85 .
  5. ↑ 1 2 Gallian, Joseph A. Un estudio dinámico del etiquetado de gráficos  // Electronic  Journal of Combinatorics : diario. — 1998; 18ª edición en 2015. - Vol. 5 . - P. Dynamic Survey 6 (electrónico), en la 1ª edición 43 páginas, en la 18ª - 389 páginas .
  6. ↑ Kotzig, Antón. Descomposiciones de grafos completos en cubos isomorfos  (inglés)  // Journal of Combinatorial Theory. Serie B  : diario. - 1981. - vol. 31 , núm. 3 . - pág. 292-296 . - doi : 10.1016/0095-8956(81)90031-9 .
  7. ↑ Weisstein, Eric W. Gráfico elegante  en el sitio web de Wolfram MathWorld .
  8. ↑ Aldred, REL; McKay, Brendan D. Etiquetado elegante y armonioso de árboles  (neopr.)  // Boletín del Instituto de Combinatoria y sus Aplicaciones. - 1998. - T. 23 . - S. 69-72 .
  9. ↑ Colmillo, Wenjie. Un enfoque computacional de la conjetura del árbol elegante  (inglés)  : revista. - 2010. - arXiv : 1003.3045 . Véase también Proyecto de verificación de árbol elegante

Literatura