Condiciones para la suma de grados implícita para árboles de expansión con pocas hojas en gráficos libres de
Autores: Cai, Junqing; Lin, Cheng-Kuan; Sun, Qiang; Wang, Panpan
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Condiciones para la suma de grados implícita para árboles de expansión con pocas hojas en gráficos libres de
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Gráfico
Abarcando
Finalizado
árboles
Importante
Condiciones
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 46
Citaciones: Sin citaciones
Un grafo con vértices se llama un -grafo. Un árbol de expansión con a lo sumo hojas se denomina árbol de expansión -terminado. Los árboles de expansión -terminados son importantes en varios campos como el diseño de redes, la teoría de grafos y las redes de comunicación. Proporcionan una forma estructurada de conectar todos los nodos en una red mientras se asegura una comunicación eficiente y se minimizan las conexiones innecesarias. Además, sirven como componentes fundamentales para algoritmos en enrutamiento, difusión y protocolos de árbol de expansión. Sin embargo, determinar si un grafo conectado tiene un árbol de expansión -terminado o no es NP-completo. Por lo tanto, es importante identificar condiciones suficientes para la existencia de tales árboles. El grado implícito propuesto por Zhu, Li y Deng es un indicador importante para el problema hamiltoniano y el problema del árbol de expansión -terminado. En este artículo, proporcionamos dos condiciones suficientes para que los grafos conectados libres de - tengan árboles de expansión -terminados para = 2, 3. Demostramos lo siguiente: Sea un -grafo conectado libre de -. Para = 2, 3, si la suma del grado implícito de cualquier + 1 vértices independientes de es al menos - + 2, entonces tiene un árbol de expansión -terminado. Además, presentamos dos ejemplos para mostrar que los límites inferiores y - 1 son los mejores posibles.
Descripción
Un grafo con vértices se llama un -grafo. Un árbol de expansión con a lo sumo hojas se denomina árbol de expansión -terminado. Los árboles de expansión -terminados son importantes en varios campos como el diseño de redes, la teoría de grafos y las redes de comunicación. Proporcionan una forma estructurada de conectar todos los nodos en una red mientras se asegura una comunicación eficiente y se minimizan las conexiones innecesarias. Además, sirven como componentes fundamentales para algoritmos en enrutamiento, difusión y protocolos de árbol de expansión. Sin embargo, determinar si un grafo conectado tiene un árbol de expansión -terminado o no es NP-completo. Por lo tanto, es importante identificar condiciones suficientes para la existencia de tales árboles. El grado implícito propuesto por Zhu, Li y Deng es un indicador importante para el problema hamiltoniano y el problema del árbol de expansión -terminado. En este artículo, proporcionamos dos condiciones suficientes para que los grafos conectados libres de - tengan árboles de expansión -terminados para = 2, 3. Demostramos lo siguiente: Sea un -grafo conectado libre de -. Para = 2, 3, si la suma del grado implícito de cualquier + 1 vértices independientes de es al menos - + 2, entonces tiene un árbol de expansión -terminado. Además, presentamos dos ejemplos para mostrar que los límites inferiores y - 1 son los mejores posibles.