Emparelhameno Perfeito em Produto Cartesiano de Grafos
Expositor: Camila S. Crispim
Instituição: PUC-Rio
Data e Horário: 30/05/19 | 16:00h

RESUMO: É conhecido da literatura que o produto cartesiano de dois grafos com emparelhamento perfeito possui emparelhamento perfeito. Em sua tese de doutorado (Propriedades do produto cartesiano de grafos. Tese de doutorado ICC/UFF, 2015), A. Almeida exibe um grafo G sem emparelhamento perfeito tal que G 2 = GG possui emparelhamento perfeito, resolvendo parcialmente uma questão em aberto. A mesma autora levanta a questão: que características do grafo G produzem este efeito? Ou seja, como caracterizar grafos sem emparelhamento perfeito cujo quadrado (via produto cartesiano) possui emparelhamento perfeito. Irei apresentar uma família de grafos Gk com n = 2k vértices, k ≥ 3, que satisfaz tal propriedade, e irei descrever um método para selecionar as n 2 2 arestas de um emparelhamento perfeito em GkGk .