This paper was published through Galoá and has a deposited DOI. To cite this paper, use one of the standards below:
In case you are one of the co-authors and want to register this paper in your Lattes, use the following code: doi > 10.59254/sbpo-2020-122633
If you've NEVER registered a DOI in your Lattes, check our 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
Now you could share with me your questions, observations and congratulations
Create a topicWatch 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.
With nearly 200,000 papers published, Galoá empowers scholars to share and discover cutting-edge research through our streamlined and accessible academic publishing platform.
Learn more about our products:
This proceedings is identified by a DOI , for use in citations or bibliographic references. Attention: this is not a DOI for the paper and as such cannot be used in Lattes to identify a particular work.
Check the link "How to cite" in the paper's page, to see how to properly cite the paper