Orlando Lee
Sexta-feira, 11 de abril de 2003, 15:15
Sala 268, Bloco A, IME-USP
Resumo:
Seja G um grafo 4-conexo e ra uma aresta de G. Neste seminário mostraremos que existe um subgrafo H (com determinadas propriedades) de G contendo ra tal que G-(V(H)-{r}) é 2-conexo. Um corolário deste resultado é a existência de um circuito C em G contendo ra tal que G-(V(C)-{r}) é 2-conexo.
O subgrafo H acima possui uma certa "estrutura" que descreveremos durante a apresentação. Ele é também o primeiro passo em direção a obter uma decomposição de grafos 4-conexos que mantém certas propriedades de conexidade. Maiores detalhes serão fornecidos no seminário.
Uma aplicação desta decomposição é a construção de quatro árvores geradoras r-independentes em um grafo 4-conexo (duas árvores geradoras T1 e T2 são r-independentes se para todo vértice v, os caminhos T1[r,v] e T2[r,v] têm apenas os vértices r e v em comum.)