Propiedades y reconocimiento de los gráficos de átomos
Autores: Simonet, Geneviève; Berry, Anne
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Propiedades y reconocimiento de los gráficos de átomos
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Grafo de átomos
Grafo conectado
Vértices
átomos
Descomposición de separadores
Aristas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 51
Citaciones: Sin citaciones
El grafo átomo de un grafo conectado es un grafo cuyos vértices son los átomos obtenidos por la descomposición del separador mínimo de cliques de este grafo, y cuyos bordes son los bordes de todos sus árboles átomo. Un grafo es un grafo átomo si hay un grafo cuyo grafo átomo es isomorfo a él. Estudiamos la clase de grafos átomo, que también es la clase de grafos átomo de grafos cordales, y el problema de reconocimiento asociado. Demostramos que cada grafo átomo es un grafo perfecto y damos una caracterización de los grafos átomo en términos de un árbol de expansión, inspirada en la caracterización de los grafos de cliques de grafos cordales como árboles expandidos. También caracterizamos los grafos cordales que tienen el mismo átomo y grafo de cliques, y resolvemos el problema de reconocimiento de los grafos átomo de dos clases de grafos.
Descripción
El grafo átomo de un grafo conectado es un grafo cuyos vértices son los átomos obtenidos por la descomposición del separador mínimo de cliques de este grafo, y cuyos bordes son los bordes de todos sus árboles átomo. Un grafo es un grafo átomo si hay un grafo cuyo grafo átomo es isomorfo a él. Estudiamos la clase de grafos átomo, que también es la clase de grafos átomo de grafos cordales, y el problema de reconocimiento asociado. Demostramos que cada grafo átomo es un grafo perfecto y damos una caracterización de los grafos átomo en términos de un árbol de expansión, inspirada en la caracterización de los grafos de cliques de grafos cordales como árboles expandidos. También caracterizamos los grafos cordales que tienen el mismo átomo y grafo de cliques, y resolvemos el problema de reconocimiento de los grafos átomo de dos clases de grafos.