En teoría de grafos , un conjunto de índice amigable 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 .
Un etiquetado amigable de 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 como 0 es lo más cercano posible al número de vértices etiquetados como 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 amigable de los vértices de G , también se pueden etiquetar las aristas: una arista dada uv se etiqueta con un 0 si sus extremos u y v tienen etiquetas iguales, y se etiqueta con un 1 si sus extremos tienen etiquetas diferentes. El índice amigable del etiquetado es el valor absoluto de la diferencia entre el número de aristas etiquetadas 0 y el número de aristas etiquetadas 1.
El conjunto de índices amigables de G , denotado FI ( G ) , es el conjunto de números que pueden surgir como índices amigables de etiquetados amigables de G . [1]
La encuesta dinámica sobre etiquetado de gráficos contiene una lista de artículos que examinan los índices amigables de varios gráficos. [2]