Etiquetado de gráficos

En la disciplina matemática de la teoría de grafos , el etiquetado de un grafo es la asignación de etiquetas, tradicionalmente representadas por números enteros , a los bordes y/o vértices de un grafo . ^[1]

Formalmente, dado un grafo G = ( V , E ) , un etiquetado de vértice es una función de V respecto de un conjunto de etiquetas; un grafo con dicha función definida se denomina grafo etiquetado por vértice . Del mismo modo, un etiquetado de arista es una función de E respecto de un conjunto de etiquetas. En este caso, el grafo se denomina grafo etiquetado por arista .

Cuando las etiquetas de los bordes son miembros de un conjunto ordenado (por ejemplo, los números reales ), se puede llamar gráfico ponderado .

Cuando se utiliza sin calificación, el término grafo etiquetado generalmente se refiere a un grafo etiquetado por vértice con todas las etiquetas distintas. Un grafo de este tipo puede etiquetarse de manera equivalente con los números enteros consecutivos { 1, …, | V | } , donde | V | es el número de vértices en el grafo. ^[1] Para muchas aplicaciones, a los bordes o vértices se les asignan etiquetas que son significativas en el dominio asociado. Por ejemplo, a los bordes se les pueden asignar pesos que representan el "costo" de atravesar entre los vértices incidentes. ^[2]

En la definición anterior, se entiende que un grafo es un grafo simple no dirigido y finito. Sin embargo, la noción de etiquetado se puede aplicar a todas las extensiones y generalizaciones de grafos. Por ejemplo, en la teoría de autómatas y la teoría del lenguaje formal es conveniente considerar multigrafos etiquetados , es decir, un par de vértices puede estar conectado por varias aristas etiquetadas. ^[3]

La mayoría de los etiquetados de gráficos tienen su origen en los etiquetados presentados por Alexander Rosa en su artículo de 1967. ^[4] Rosa identificó tres tipos de etiquetados, a los que llamó etiquetados α , β y ρ . ^{[5] Los etiquetados} β fueron posteriormente renombrados como "elegantes" por Solomon Golomb , y el nombre ha sido popular desde entonces.

Un grafo se considera elegante si sus vértices están etiquetados de 0 a | E | , el tamaño del grafo, y si este etiquetado de vértice induce un etiquetado de arista de 1 a | 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 vértices etiquetados i y j , entonces e será etiquetado | i − j | . Por lo tanto, un grafo G = ( V , E ) es elegante si y solo si existe una inyección desde V a {0, ..., | E |} que induce una biyección desde E a {1, ..., | E |} .

En su artículo original, Rosa demostró que todos los grafos eulerianos con un tamaño equivalente a 1 o 2 ( mod 4 ) no son gráciles. Si ciertas familias de grafos son gráciles o no es un área de la teoría de grafos que se encuentra bajo un estudio extenso. Podría decirse que la conjetura no probada más grande en el etiquetado de grafos es la conjetura de Ringel-Kotzig, que plantea la hipótesis de que todos los árboles son gráciles. Esto ha sido probado para todos los caminos , orugas y muchas otras familias infinitas de árboles. El propio Anton Kotzig ha llamado al esfuerzo por probar la conjetura una "enfermedad". ^[6]

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

Los etiquetados con bordes elegantes fueron introducidos por primera vez por Sheng-Ping Lo en 1985. ^[7]

Una condición necesaria para que un gráfico tenga aristas elegantes 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 arista para una arista ( x , y ) como la suma de las etiquetas de los dos vértices x , y (mod k ) . Un "grafo armonioso" es uno que tiene un etiquetado armonioso. Los ciclos impares son armoniosos, al igual que los grafos de Petersen . Se conjetura que los árboles son todos armoniosos si se permite reutilizar una etiqueta de vértice. ^{[8] El} libro de siete páginas graph K _1,7 × K ₂ proporciona un ejemplo de un grafo que no es armonioso. ^[9]

La coloración de un gráfico es una subclase de las etiquetas de gráficos. 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]

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