Etiquetado de gráficos

Un grafo se denomina elegante si sus vértices están etiquetados del 0 al | E | , el tamaño del grafo, y si este etiquetado de vértices induce un etiquetado de aristas del 1 al | E | . Para cualquier arista e , la etiqueta de e es la diferencia positiva entre las etiquetas de los dos vértices incidentes con e . En otras palabras, si e es incidente con los vértices etiquetados i y j , entonces e estará etiquetado como | i − j | . Por lo tanto, un grafo G = ( V , E ) es elegante si y solo si existe una inyección de V a {0, ..., | E | } que induce una biyección de E a {1, ..., | E | } .

En su artículo original, Rosa demostró que todos los grafos eulerianos con tamaño equivalente a 1 o 2 ( mod 4 ) no son elegantes. La elegancia de ciertas familias de grafos es un área de la teoría de grafos que se estudia extensamente. Podría decirse que la mayor conjetura sin demostrar en el etiquetado de grafos es la conjetura de Ringel-Kotzig, que plantea la hipótesis de que todos los árboles son elegantes. Esto se ha demostrado para todos los caminos , orugas y muchas otras familias infinitas de árboles. El propio Anton Kotzig ha calificado el esfuerzo por demostrar la conjetura como una "enfermedad". ^{[ 6 ]}

Un etiquetado de aristas con aristas suaves en un grafo simple sin bucles ni aristas múltiples en p vértices y q aristas es un etiquetado de las aristas mediante enteros distintos en {1, …, q } tal que el etiquetado de los vértices inducido al etiquetar un vértice con la suma de las aristas incidentes módulo p asigna a los vértices todos los valores desde 0 hasta p − 1. Se dice que un grafo G es "con aristas suaves" si admite un etiquetado de aristas suaves.

El etiquetado Edge-Graceful fue introducido por primera vez por Sheng-Ping Lo en 1985. ^{[ 7 ]}

Una condición necesaria para que un grafo sea elegante en sus aristas es la "condición de Lo":

${\displaystyle q(q+1)={\frac {p(p-1)}{2}}\mod p.}$

Un "etiquetado armonioso" en un grafo G es una inyección desde los vértices de G al grupo de enteros módulo k , donde k es el número de aristas de G , que induce una biyección entre las aristas de G y los números módulo k al tomar la etiqueta de una arista ( x , y ) como la suma de las etiquetas de los dos vértices x , y (mod k ) . Un "grafo armonioso" es aquel que tiene un etiquetado armonioso. Los ciclos impares son armoniosos, al igual que los grafos de Petersen . Se conjetura que todos los árboles son armoniosos si se permite la reutilización de una etiqueta de vértice. _[ ^{8 ] El} grafo de libro _de siete páginas K1,7 × K2 proporciona un ejemplo de un grafo que no es armonioso. ^{[ 9 ]}

Una coloración de grafos es una subclase de las etiquetas de grafos. Las coloraciones de vértices asignan etiquetas diferentes a los vértices adyacentes, mientras que las coloraciones de aristas asignan etiquetas diferentes a las aristas adyacentes. ^{[ 10 ]}

Una asignación de números positivos a un grafo G es una asignación de enteros positivos a los vértices de G tal que si S ( v ) denota la suma de las etiquetas de los vecinos de v , entonces S es una coloración de vértices de G. El "número de la suerte" de G es el menor k tal que G tiene una asignación de números positivos con los enteros {1, …, k }. ^{[ 11 ]}

Un etiquetado antimágico de un grafo G es una asignación biunívoca de los enteros positivos {1,..., | E | } a las aristas de G de tal manera que todos los pesos de los vértices inducidos sean distintos, donde el peso de un vértice es la suma de las etiquetas de todas las aristas incidentes a él. ^{[ 12 ]}

Una asignación mágica (por distancia) de un grafo G consiste en la asignación biyectiva de los enteros positivos {1,..., | V | } a los vértices de G, de manera que el peso de cada vértice sea igual a un entero positivo k . El peso de un vértice es la suma de las etiquetas de todos los vértices adyacentes. Dicha constante k , si existe, se denomina constante mágica del grafo.