Programa de Pós-graduação em Ciência da Computação em Rede
URI Permanente desta comunidade
Navegar
Navegando Programa de Pós-graduação em Ciência da Computação em Rede por Autor "Duarte, Márcio Antônio"
Agora exibindo 1 - 1 de 1
Resultados por página
Opções de Ordenação
Item Sobre convexidade em prismas complementares(Universidade Federal de Goiás, 2015-04-10) Duarte, Márcio Antônio; Szwarcfiter, Jayme L.; http://lattes.cnpq.br/2002515486942024; Barbosa, Rommel Melgaço; http://lattes.cnpq.br/6228227125338610; Barbosa, Rommel Melgaço; Yanasse, Horacio Hideki; Oliveira, Carla Silva; Coelho, Erika Morais Martins; Silva, Hebert Coelho daIn this work, we present some related results, especially the properties algoritimics and of complexity of a product of graphs called complementary prism. Answering some questions left open by Haynes, Slater and van der Merwe, we show that the problem of click, independent set and k-dominant set is NP-Complete for complementary prisms in general. Furthermore, we show NP-completeness results regarding the calculation of some parameters of the P3-convexity for the complementary prism graphs in general, as the P3-geodetic number, P3-hull number and P3-Carathéodory number. We show that the calculation of P3-geodetic number is NP-complete for complementary prism graphs in general. As for the P3-hull number, we can show that the same can be efficiently computed in polynomial time. For the P3-Carathéodory number, we show that it is NPcomplete complementary to prisms bipartite graphs, but for trees, this may be calculated in polynomial time and, for class of cografos, calculating the P3-Carathéodory number of complementary prism of these is 3. We also found a relationship between the cardinality Carathéodory set of a graph and a any Carathéodory set of complementary prism. Finally, we established an upper limit calculation the parameters: geodetic number, hull number and Carathéodory number to operations complementary prism of path, cycles and complete graphs considering the convexities P3 and geodesic.