Orlando Lee
Sexta-feira, 28 de março de 2003, 15:15
Sala 268, Bloco A, IME-USP
Resumo:
Dada uma árvore T e vértices x,y de V(T), denotamos por T[x,y] o (único) caminho de x a y em T. Sejam T1 e T2 duas árvores com um mesmo conjunto de vértices, e seja r um certo vértice de ambas as árvores. Dizemos que 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.
O problema de interesse é o seguinte: dado um grafo G e um vértice r de G, encontrar o maior número de árvores geradoras de G que sejam (duas a duas) r-independentes.
Itai e Zehavi propuseram a seguinte conjectura: se G é um grafo k-conexo e r é um vértice qualquer de G, então G contém k árvores geradoras r-independentes.
Neste seminário discutiremos os casos particulares dessa conjectura em que k=1,2,3, e (caso haja tempo) o caso em que k=4 e G é planar. Para k>=5, a conjectura de Itai e Zehavi continua em aberto.
Em outro seminário discutiremos o caso em que k=4 e G é um grafo 4-conexo arbitrário. Este caso foi resolvido recentemente por Curran, Lee e Yu.