k-independência em grafos P4-esparsos

Vol 54, 2022 - 152990
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

Um conjunto de vértices S de um grafo G é k-independente se cada um de seus vértices é adjacente a no máximo k-1 vértices do conjunto S, onde k é um inteiro positivo. O número de k-independência é a cardinalidade de um maior conjunto k-independente em um grafo G. Determinar o número de k-independencia é um problema NP-difícil para grafos gerais. Apresentamos fórmulas fechadas para o número de k-independência em grafos P4-esparsos em termos do número de k-independência de seus fatores e apresentamos um algoritmo de tempo polinomial que retorna o número de k-independência de um grafo P4-esparso.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal de Goiás
Eixo Temático
  • 19 - TAG – Teoria e Algoritmos em Grafos
Palavras-chave
k-independência
grafos P4-esparsos
Cografos