logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro