Un límite superior para el número de dominación romana eterna
Autores: Brewster, Richard; MacGillivray, Gary; Williams, Ethan
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Un límite superior para el número de dominación romana eterna
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Guardias móviles
Vértices
Gráfico
Ataques
Conjunto romano-dominante
árbol
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 26
Citaciones: Sin citaciones
Imagina usar guardias móviles para defender los vértices de un grafo de una secuencia de ataques sujetos a las condiciones de que después de cada ataque: (i) cada guardia permanece en su lugar o se mueve a un vértice adyacente; (ii) la configuración de guardias forma un conjunto de dominación romana; y (iii) hay al menos un guardia en cada vértice atacado. Mostramos que siempre es posible defender los vértices de un árbol con vértices usando como máximo guardias y que este límite es ajustado.
Descripción
Imagina usar guardias móviles para defender los vértices de un grafo de una secuencia de ataques sujetos a las condiciones de que después de cada ataque: (i) cada guardia permanece en su lugar o se mueve a un vértice adyacente; (ii) la configuración de guardias forma un conjunto de dominación romana; y (iii) hay al menos un guardia en cada vértice atacado. Mostramos que siempre es posible defender los vértices de un árbol con vértices usando como máximo guardias y que este límite es ajustado.