Conectividad de Hamilton de politopos convexos con aplicaciones a su índice de desvío.
Autores: Hayat, Sakander; Khan, Asad; Khan, Suliman; Liu, Jia-Bao
Idioma: Inglés
Editor: Hindawi
Año: 2021
Acceso abierto
Artículo científico
Categoría
Ingeniería y Tecnología
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 26
Citaciones: Sin citaciones
Un grafo conectado se llama Hamilton-conectado si existe un camino hamiltoniano entre cualquier par de sus vértices. Determinar si un grafo es Hamilton-conectado es un problema NP-completo. Los grafos hamiltonianos y Hamilton-conectados tienen diversas aplicaciones en informática e ingeniería eléctrica. El índice de desvío de un grafo se define como la suma de las longitudes de los desvíos entre todos los pares no ordenados de vértices. El índice de desvío tiene diversas aplicaciones en química. Calcular el índice de desvío para un grafo también es un problema NP-completo. En este artículo, estudiamos la Hamilton-conectividad de poliedros convexos. Construimos tres familias infinitas de poliedros convexos y mostramos que son Hamilton-conectados. También se construye una familia infinita de poliedros convexos no Hamilton-conectados, lo que a su vez muestra que no todos los poliedros convexos son Hamilton-conectados. Utilizando la conectividad de Hamilton de estas familias de grafos, calculamos fó
Descripción
Un grafo conectado se llama Hamilton-conectado si existe un camino hamiltoniano entre cualquier par de sus vértices. Determinar si un grafo es Hamilton-conectado es un problema NP-completo. Los grafos hamiltonianos y Hamilton-conectados tienen diversas aplicaciones en informática e ingeniería eléctrica. El índice de desvío de un grafo se define como la suma de las longitudes de los desvíos entre todos los pares no ordenados de vértices. El índice de desvío tiene diversas aplicaciones en química. Calcular el índice de desvío para un grafo también es un problema NP-completo. En este artículo, estudiamos la Hamilton-conectividad de poliedros convexos. Construimos tres familias infinitas de poliedros convexos y mostramos que son Hamilton-conectados. También se construye una familia infinita de poliedros convexos no Hamilton-conectados, lo que a su vez muestra que no todos los poliedros convexos son Hamilton-conectados. Utilizando la conectividad de Hamilton de estas familias de grafos, calculamos fó