Sobre convexidade em prismas complementares
Carregando...
Data
2015-04-10
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
In 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.
Descrição
Palavras-chave
Citação
DUARTE, M. A. Sobre convexidade em prismas complementares. 2015. 68 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2015.