logo móvil
Contáctanos

sobre el número total de dominación externa-independiente de grafos

Autores: Cabrera-Martínez, Abel; Hernández-Gómez, Juan Carlos; Parra-Inza, Ernesto; Sigarreta Almira, José María

Idioma: Inglés

Editor: MDPI

Año: 2020

Descargar PDF

Acceso abierto

Artículo científico
2020

sobre el número total de dominación externa-independiente de grafos


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Conjunto dominante total
Conjunto dominante total externamente independiente
Grado máximo
Subgrafo inducido
Número de dominación total externamente independiente
Problema NP-duro

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 34

Citaciones: Sin citaciones


Descripción
Un conjunto de vértices de un grafo es un conjunto dominante total si cada vértice está conectado a al menos un vértice en dicho conjunto. Decimos que un conjunto dominante total es un conjunto dominante total externo-independiente si el grado máximo del subgrafo inducido por los vértices que no están en él es menor o igual a k. La cardinalidad mínima entre todos los conjuntos dominantes totales externos-independientes es el número de dominación total externo-independiente de G. En este artículo, presentamos este parámetro y comenzamos con el estudio de sus propiedades combinatorias y computacionales. Por ejemplo, proporcionamos varias relaciones cerradas entre este nuevo parámetro y otros relacionados con la dominación y la independencia en los grafos. Además, presentamos varios resultados de tipo Nordhaus-Gaddum. Finalmente, demostramos que calcular el número de dominación total externo-independiente de un grafo es un problema NP-duro.

Otros recursos que podrían interesarte

Temas Virtualpro