En teoría de grafos , un conjunto de índice amigable es un conjunto finito de enteros asociados con un gráfico no dirigido dado y generado por un tipo de etiquetado de gráfico llamado etiquetado amigable .
Un etiquetado amigable de un gráfico 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 a el número de vértices etiquetados como 1: deben ser iguales (para gráficos con un número par de vértices) o diferir en uno (para gráficos con un número impar de vértices).
Dado un etiquetado amable de los vértices de G , también se puede etiquetar los bordes: un borde dado uv está marcado con un 0 si sus puntos finales U y V tienen etiquetas iguales, y que está marcado con un 1 si sus puntos finales tienen diferentes etiquetas. El índice amigable del etiquetado es el valor absoluto de la diferencia entre el número de bordes etiquetados como 0 y el número de bordes etiquetados como 1.
El conjunto de índices amable de G , denotado FI ( G ) , es el conjunto de números que pueden surgir como índices amistosas de marcajes amistosas de G . [1]
La Encuesta dinámica de etiquetado de gráficos contiene una lista de artículos que examinan los índices amigables de varios gráficos. [2]
Referencias
- ^ Kwong, Harris; Lee, Sin-Min; Ng, Ho (2008). "En conjuntos de índices amigables de 2 gráficos regulares" . Matemáticas discretas . 308 (23): 5522–5532. doi : 10.1016 / j.disc.2007.10.018 . Señor 2459372 .
- ^ Gallian, Joseph A (2009). "Un estudio dinámico de etiquetado de gráficos" (PDF) . El. J. Combinat . 16 (# DS6). Archivado desde el original (PDF) el 20 de noviembre de 2004.