logo móvil
Contáctanos

Dominación de coloración de grafos

Autores: Zhou, Yangyang; Zhao, Dongyang; Ma, Mingyuan; Xu, Jin

Idioma: Inglés

Editor: MDPI

Año: 2022

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro