Etiquetado elegante

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 enteros de 0 a m inclusive, de tal manera que no haya dos vértices que compartan una etiqueta, y cada arista se identifique de forma única por la diferencia absoluta entre sus extremos, de modo que esta magnitud se encuentre entre 1 y m inclusive. ^{[ 1 ]} Un grafo que admite un etiquetado elegante se llama grafo elegante .

El nombre "etiquetado elegante" se debe a Solomon W. Golomb ; este tipo de etiquetado fue originalmente denominado etiquetado β por Alexander Rosa en un artículo de 1967 sobre etiquetado de grafos. ^{[ 2 ]}

Un problema abierto importante 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 como GTC (que no debe confundirse con la conjetura de Kotzig sobre grafos conexos por caminos regulares). ^{[ 3 ]} Esta conjetura plantea la hipótesis de que todos los árboles son elegantes. Sigue siendo una conjetura abierta, aunque una conjetura relacionada pero más débil conocida como "la conjetura de Ringel" fue demostrada parcialmente en 2020. ^{[ 4 ] [ 5 ] [ 6 ]} Kotzig una vez llamó al esfuerzo por demostrar 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 los enteros en [0, m + 1] de tal manera que no haya dos vértices que compartan una etiqueta, y cada arista se identifica de forma única por la diferencia absoluta entre sus puntos extremos (esta magnitud se encuentra en [1, m + 1] ).

Otra conjetura en la teoría de grafos es la conjetura de Rosa , que lleva el nombre de Alexander Rosa, y que afirma que todos los cactus triangulares son elegantes o casi elegantes. ^{[ 8 ]}

Se conjetura que un grafo elegante con aristas de 0 a m tiene no menos de${\displaystyle \left\lceil {\sqrt {3m+{\tfrac {9}{4}}}}\right\rfloor }$vértices, debido a los resultados de la regla dispersa . Esta conjetura se ha verificado para todos los grafos con 213 o menos aristas. Una conjetura relacionada es que el grafo elegante de valencia 2 m más pequeño tiene${\displaystyle 3m^{2}}$bordes, con el caso de valencia 6 que se muestra a continuación.

• En su artículo original, Rosa demostró que un grafo euleriano con 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 solo si n ≡ 0 (mod 4) o n ≡ 3 (mod 4).
• Todos los grafos de ruta y los grafos de oruga son elegantes. ^{[ 2 ]}
• Todos los gráficos de langosta con una coincidencia perfecta son elegantes. ^{[ 9 ]}
• Todos los árboles con un máximo de 27 vértices son elegantes; este resultado fue demostrado por Aldred y McKay en 1998 mediante un programa informático. ^{[ 10 ] [ 11 ]} Esto se extendió a árboles con un máximo de 29 vértices en la tesis de licenciatura de Michael Horton. ^{[ 12 ]} Otra extensión de este resultado hasta árboles con 35 vértices fue afirmada en 2010 por el Proyecto de Verificación de Árboles Elegantes, un proyecto de computación distribuida liderado por Wenjie Fang. ^{[ 13 ]}
• Todos los gráficos de ruedas , gráficos de redes, 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 grafos conexos simples con cuatro o menos vértices son elegantes. Los únicos grafos conexos simples no elegantes con cinco vértices son el ciclo de 5 vértices ( pentágono ); el grafo completo K ₅ ; y el grafo mariposa . ^{[ 15 ]}

• Etiquetado con bordes elegantes
• Lista de conjeturas

• Vídeo de Numberphile sobre la conjetura del árbol elegante
• Etiquetado elegante en el mundo de las matemáticas

• (K. Eshghi) Introducción a los grafos elegantes , Universidad Tecnológica Sharif, 2002.
• (UN Deshmukh y Vasanti N. Bhat-Nayak), Nuevas familias de elegantes plataneros – Actas de Ciencias Matemáticas, 1996 – Springer
• (M. Haviar, M. Ivaska), Etiquetado de vértices de grafos simples, Investigación y exposición en matemáticas, volumen 34, 2015.
• ( Ping Zhang ), Una visión caleidoscópica de las coloraciones de grafos, SpringerBriefs in Mathematics, 2016 – Springer