-Graficos de árboles
Autores: Finbow, Stephen; van Bommel, Christopher M.
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
-Graficos de árboles
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Grafos
Conjuntos dominantes mínimos
Algoritmo
árboles
Grafos de producto cartesiano
Conexiones
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 25
Citaciones: Sin citaciones
Para un grafo G, el -grafo de G, denotado , es el grafo cuyo conjunto de vértices es la colección de conjuntos dominantes mínimos, o -conjuntos de G, y dos -conjuntos son adyacentes en si difieren por un solo vértice y los dos vértices diferentes son adyacentes en . En este artículo, consideramos -gráficos de árboles. Desarrollamos un algoritmo para determinar el -grafo de un árbol, caracterizamos qué árboles son -gráficos de árboles, y además comentamos sobre la estructura de los -gráficos de árboles y sus conexiones con los gráficos de producto cartesiano, el conjunto de gráficos que se pueden obtener a partir del producto cartesiano de gráficos de orden al menos dos.
Descripción
Para un grafo G, el -grafo de G, denotado , es el grafo cuyo conjunto de vértices es la colección de conjuntos dominantes mínimos, o -conjuntos de G, y dos -conjuntos son adyacentes en si difieren por un solo vértice y los dos vértices diferentes son adyacentes en . En este artículo, consideramos -gráficos de árboles. Desarrollamos un algoritmo para determinar el -grafo de un árbol, caracterizamos qué árboles son -gráficos de árboles, y además comentamos sobre la estructura de los -gráficos de árboles y sus conexiones con los gráficos de producto cartesiano, el conjunto de gráficos que se pueden obtener a partir del producto cartesiano de gráficos de orden al menos dos.