Número de aislamiento versus número de dominación de árboles
Autores: Lemanska, Magdalena; Souto-Salorio, María José; Dapena, Adriana; Vazquez-Araujo, Francisco J.
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Número de aislamiento versus número de dominación de árboles
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Grafo
Conjunto aislante
Número de aislamiento
Conjunto dominante
Número de dominación
árboles
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 33
Citaciones: Sin citaciones
Si es un grafo de orden , llamamos a un conjunto aislante si el grafo inducido por no contiene aristas. La cardinalidad mínima de un conjunto aislante de se llama el número de aislamiento de , y se denota por . Se sabe que y el límite es exacto. Un subconjunto se llama dominante en si . La cardinalidad mínima de un conjunto dominante de es el número de dominación, y se denota por . En este documento, analizamos una familia de árboles donde , y demostramos que implica Además, damos diferentes caracterizaciones equivalentes de tales grafos y proponemos algoritmos simples para construir estos árboles a partir de las conexiones de estrellas.
Descripción
Si es un grafo de orden , llamamos a un conjunto aislante si el grafo inducido por no contiene aristas. La cardinalidad mínima de un conjunto aislante de se llama el número de aislamiento de , y se denota por . Se sabe que y el límite es exacto. Un subconjunto se llama dominante en si . La cardinalidad mínima de un conjunto dominante de es el número de dominación, y se denota por . En este documento, analizamos una familia de árboles donde , y demostramos que implica Además, damos diferentes caracterizaciones equivalentes de tales grafos y proponemos algoritmos simples para construir estos árboles a partir de las conexiones de estrellas.