Este trabalho foi publicado pelo Galoá e tem um DOI depositado. Para citar este trabalho, use um dos padrões abaixo:
Caso você seja um dos co-autores e queira cadastrar esse trabalho no seu Currículo Lattes, use o seguinte código: doi > 10.59254/sbpo-2020-122633
Se você NUNCA registrou um DOI no seu Lattes, veja nosso tutorial!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
Agora você poderia compartilhar comigo suas dúvidas, observações e parabenizações
Crie um tópicoWatch this next:
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.
Com ~200 mil publicações revisadas por pesquisadores do mundo todo, o Galoá impulsiona cientistas na descoberta de pesquisas de ponta por meio de nossa plataforma indexada.
Confira nossos produtos e como podemos ajudá-lo a dar mais alcance para sua pesquisa:
Esse proceedings é identificado por um DOI , para usar em citações ou referências bibliográficas. Atenção: este não é um DOI para o jornal e, como tal, não pode ser usado em Lattes para identificar um trabalho específico.
Verifique o link "Como citar" na página do trabalho, para ver como citar corretamente o artigo