logo móvil
Contáctanos

Total 2-Dominación Arcoiris en Gráficos

Autores: Jiang, Huiqin; Rao, Yongsheng

Idioma: Inglés

Editor: MDPI

Año: 2022

Descargar PDF

Acceso abierto

Artículo científico


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Número de dominación ponderado del gráfico
Función de dominación k-arcoíris total
Peso
Número de dominación
NP-completo
Complejidad

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 33

Citaciones: Sin citaciones


Descripción
Una función de dominación total k-arcoíris en un grafo es una función tal que (i) para cada vértice con , (ii) para . El peso de una función de dominación total 2-arcoíris se denota por . El número total de dominación arcoíris k de es el peso mínimo de una función de dominación total k-arcoíris de . El problema de dominación total 2-arcoíris mínimo (MT2RDP) consiste en encontrar el número total de dominación arcoíris 2 del grafo de entrada. En este documento, estudiamos el número total de dominación arcoíris 2 de los grafos. Demostramos que el MT2RDP es NP-completo para grafos bipartitos planares, grafos bipartitos cordales, grafos de caminos no dirigidos y grafos divididos. Luego, se propone un algoritmo de tiempo lineal para calcular el número total de dominación arcoíris k de árboles. Finalmente, estudiamos la diferencia en complejidad entre MT2RDP y el problema mínimo de dominación arcoíris 2.

Documentos Relacionados

Temas Virtualpro