Total 2-Dominación Arcoiris en Gráficos
Autores: Jiang, Huiqin; Rao, Yongsheng
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
Categoría
Matemáticas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 30
Citaciones: Sin citaciones
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.
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.