Prismas complementares de cografos: uma classe 4-admissível sem exemplares 3-admissíveis

Favoritar este trabalho
Como citar esse trabalho?
Detalhes
  • Tipo de apresentação: Trabalho completo (oral)
  • Eixo temático: 19. TAG – Teoria e Algoritmos em Grafos
  • Palavras chaves: t-admissibilidade; Prismas Complementares; Cografos;
  • 1 Universidade Federal Rural do Rio de Janeiro
  • 2 Universidade Federal Fluminense

Prismas complementares de cografos: uma classe 4-admissível sem exemplares 3-admissíveis

Ighor Bruno de Brito

Universidade Federal Rural do Rio de Janeiro

Resumo

O problema da t-admissibilidade consiste em, dado um grafo G, encontrar uma árvore geradora T de G, em que cada par de vértices adjacentes de G, esteja a uma distância menor ou igual a t em T. Neste caso, chamamos G de t-admissível. O menor t tal que G seja t-admissível é o índice de extensão de G. Um prisma complementar de um grafo G, denotado por GG', é obtido pela união de G com seu complemento G' e a adição de um emparelhamento perfeito entre os vértices correspondentes de G e G'. Um cografo é um grafo sem caminhos induzidos com 4 vértices. Um dos desafios da t-admissibilidade é determinar classes de grafos que sejam 3-admissíveis, visto que a complexidade computacional deste problema permanece em aberto há mais de 25 anos. Além disso, sabemos que reconhecer grafos 4-admissíveis é, em geral, um problema NP-completo. Neste trabalho, mostramos que todo prisma complementar de cografo é 4-admissível, caracterizamos os prismas complementares de cografos com índice de extensão 2 e, curiosamente, mostramos que não existem prismas complementares de cografos com índice de extensão igual a 3.

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!