Conjunto de índices amigables

En teoría de grafos , un conjunto de índices amigables es un conjunto finito de números enteros asociados con un grafo no dirigido dado y generado por un tipo de etiquetado de grafos llamado etiquetado amigable .

Una forma amigable de etiquetar un grafo no dirigido de n vértices G = ( V , E ) se define como una asignación de los valores 0 y 1 a los vértices de G con la propiedad de que el número de vértices etiquetados con 0 sea lo más cercano posible al número de vértices etiquetados con 1: deben ser iguales (para grafos con un número par de vértices) o diferir en uno (para grafos con un número impar de vértices).

Dado un etiquetado descriptivo de los vértices de G , también se pueden etiquetar las aristas: una arista uv se etiqueta con un 0 si sus extremos u y v tienen etiquetas iguales, y con un 1 si sus extremos tienen etiquetas diferentes. El índice descriptivo del etiquetado es el valor absoluto de la diferencia entre el número de aristas etiquetadas con 0 y el número de aristas etiquetadas con 1.

El conjunto de índices amigables de G , denotado FI ( G ) , es el conjunto de números que pueden surgir como índices amigables de etiquetas amigables de G. ^{[ 1 ]}

El Dynamic Survey of Graph Labeling contiene una lista de artículos que examinan los índices amigables de varios grafos. ^{[ 2 ]}