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
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
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.
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.