Dominación de coloración de grafos
Autores: Zhou, Yangyang; Zhao, Dongyang; Ma, Mingyuan; Xu, Jin
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Dominación de coloración de grafos
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Coloración de dominación
Grafo
Vértice
Número cromático de dominación
NP-completitud
Complejidad
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 22
Citaciones: Sin citaciones
Una coloración de dominación de un grafo es una coloración adecuada de vértices tal que cada vértice domina al menos una clase de color (posiblemente su propia clase), y cada clase de color es dominada por al menos un vértice. El número mínimo de colores entre todas las coloraciones de dominación se llama número cromático de dominación, denotado por . En este documento, estudiamos la complejidad del problema de coloración de dominación por medio de la demostración de su NP-completitud para grafos arbitrarios. Presentamos resultados y propiedades básicas de , incluyendo los límites y resultados de caracterización, y una investigación adicional de algunas clases especiales de grafos, como los grafos bipartidos, los grafos generalizados de Petersen, productos de corona y productos de corona de aristas. Se presentan varios resultados sobre grafos con . Además, se propone una aplicación de las coloraciones de dominación en redes sociales.
Descripción
Una coloración de dominación de un grafo es una coloración adecuada de vértices tal que cada vértice domina al menos una clase de color (posiblemente su propia clase), y cada clase de color es dominada por al menos un vértice. El número mínimo de colores entre todas las coloraciones de dominación se llama número cromático de dominación, denotado por . En este documento, estudiamos la complejidad del problema de coloración de dominación por medio de la demostración de su NP-completitud para grafos arbitrarios. Presentamos resultados y propiedades básicas de , incluyendo los límites y resultados de caracterización, y una investigación adicional de algunas clases especiales de grafos, como los grafos bipartidos, los grafos generalizados de Petersen, productos de corona y productos de corona de aristas. Se presentan varios resultados sobre grafos con . Además, se propone una aplicación de las coloraciones de dominación en redes sociales.