CARACTERIZANDO MENORES BORBOLETAS E GRADES CILÍNDRICAS

Resumo

Um resultado clássico de Erdös e Pósa afirma que existe uma função f:N->N tal que, para todo k, todo grafo G contém k ciclos disjuntos em vértices dois a dois ou um conjunto T de no máximo f(k) vértices tal que G - T é acíclico. G é um menor de H se G é obtido de um subgrafo de H por uma sequência de contrações de arestas. Se G é um digrafo e as contrações na definição anterior forem restringidas para contrações borboleta, isso resultará na definição de um menor borboleta. Um grafo G possui a propriedade de Erdös-Pósa para menores se existe uma função f:N->N tal que, para todo k, todo grafo H contém k cópias de G disjuntas em vértices como um menor ou um conjunto T de no máximo f(k) vértices tal que G não é um menor de H - T. Trocando grafo por digrafo e menor por menor borboleta, a definição anterior pode ser adaptada para a propriedade de Erdös-Pósa para menores borboleta em digrafos. Os resultados de Erdö e Pósa e Reed foram generalizados por Robertson e Seymour para grafos não direcionados e por Amiri para digrafos. Robertson e Seymour provaram que um grafo não direcionado G tem tem a propriedade de Erdös-Pósa para menores se e somente se G é planar. Amiri provou que um digrafo forte D tem a propriedade de Erdös-Pósa para menores borboleta se e somente se D é menor borboleta de uma grade cilíndrica. Os resultados de Robertson, Seymour e Amiri são similares já que um grafo não direcionado é planar se e somente se ele é menor de uma grade. Diferente do caso não direcionado, nem todo digrafo planar é menor borboleta de uma grade cilíndrica. Neste contexto, estudou-se a caracterização dos digrafos que são menores borboleta de uma grade cilíndrica ou não e quais são as suas propriedades. A pesquisa alcançou como resultado propriedades necessárias e suficientes para que um digrafo seja um menor borboleta de uma grade cilíndrica, além de identificar estruturas que inviabilizam isso.