Resumen

Sea un grafo y un entero. Un subconjunto de vértices en un grafo se llama un conjunto independiente de -componentes de si cada componente de tiene un orden de a lo sumo . El número de independencia de -componentes, denotado por , es el orden máximo de un subconjunto de vértices que induce un subgrafo con orden máximo de componente a lo sumo . Probamos que si un árbol es de orden , entonces . La cota es ajustada. Además, presentamos un algoritmo de tiempo lineal para encontrar un conjunto independiente de -componentes máximo de un árbol.

• Materias:Modelo Matemático Gestión ambiental Sistemas dinámicos Datos estructurales Sistema inalámbrico
• Subjects:Mathematical model Environmental management Dynamic systems Structural data Wireless system
• Palabras claves:Grafo; Entero; Componente; Conjunto independiente; Orden; árbol
• Keywords:Graph; Integer; Component; Independent set; Order; Tree