Coverabilidad de grafos por subgrafos regulares de paridad
Autores: Petruevski, Mirko; krekovski, Riste
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Coverabilidad de grafos por subgrafos regulares de paridad
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Grafo
Par
Impar
Subgrafos
Alcanzabilidad
Arista
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
Un grafo es par (respectivamente impar) si todos sus grados de vértices son pares (respectivamente impares). Consideramos coberturas de aristas por un número prescrito de subgrafos pares y/o impares. En vista del Teorema del Flujo 8, un grafo admite una cobertura por tres subgrafos pares si y solo si es sin puentes. La cobertura por tres subgrafos impares ha sido caracterizada recientemente [Petruevski, M.; krekovski, R. Cobertura de grafo por tres subgrafos impares. , , 304-321]. No es difícil argumentar que todo grafo acíclico puede ser descompuesto en dos subgrafos impares, lo que implica que todo grafo admite una descomposición en dos subgrafos impares y uno par. Aquí, demostramos que todo grafo con 3-conexión de aristas es cubrible por dos subgrafos pares y uno impar. El resultado es preciso en términos de conectividad de aristas. También discutimos la cobertura por más de tres subgrafos regulares de paridad, y demostramos que se puede decidir eficientemente si existe una instancia dada de tal cobertura. Además, deducimos aquí un algoritmo de tiempo polinómico que determina si un conjunto dado de aristas se extiende a un subgrafo impar. Finalmente, compartimos algunas reflexiones sobre la cobertura por dos subgrafos y concluimos con dos conjeturas.
Descripción
Un grafo es par (respectivamente impar) si todos sus grados de vértices son pares (respectivamente impares). Consideramos coberturas de aristas por un número prescrito de subgrafos pares y/o impares. En vista del Teorema del Flujo 8, un grafo admite una cobertura por tres subgrafos pares si y solo si es sin puentes. La cobertura por tres subgrafos impares ha sido caracterizada recientemente [Petruevski, M.; krekovski, R. Cobertura de grafo por tres subgrafos impares. , , 304-321]. No es difícil argumentar que todo grafo acíclico puede ser descompuesto en dos subgrafos impares, lo que implica que todo grafo admite una descomposición en dos subgrafos impares y uno par. Aquí, demostramos que todo grafo con 3-conexión de aristas es cubrible por dos subgrafos pares y uno impar. El resultado es preciso en términos de conectividad de aristas. También discutimos la cobertura por más de tres subgrafos regulares de paridad, y demostramos que se puede decidir eficientemente si existe una instancia dada de tal cobertura. Además, deducimos aquí un algoritmo de tiempo polinómico que determina si un conjunto dado de aristas se extiende a un subgrafo impar. Finalmente, compartimos algunas reflexiones sobre la cobertura por dos subgrafos y concluimos con dos conjeturas.