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

Favorite this paper
How to cite this paper?
Details
  • Presentation type: Trabalho completo (oral)
  • Track: 19. TAG – Teoria e Algoritmos em Grafos
  • Keywords: 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

Abstract

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.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!