Grafos de Interseção em Arestas de Caminhos em uma Árvore

O grafo de interseção de uma família de conjuntos é o grafo obtido associando-se a cada conjunto um vértice e, tal que dois vértices são adjacentes se e somente se os conjuntos correspondentes têm interseção não vazia. Examinamos neste trabalho a classe dos grafos UE, que são os grafos de interseção de famílias de caminhos em uma árvore, onde os caminhos são considerados como conjuntos de arestas. Se a família de caminhos satisfaz a propriedade Helly, temos a classe U E H. Quando a árvore é direcionada ou direcionada e enraizada, temos respectivamente as classes DE e RDE. Se os caminhos são considerados como conjuntos de vértices, temos as classes UV, DV e RDV, definidas de maneira análoga às classes DE e RDE. Neste trabalho consideramos propriedades estruturais dos grafos UE e dos grafos UEH, incluindo métodos de decomposição destes grafos que conduzem à caracterizações. No caso dos grafos UEH esta caracterização conduz à um algoritmo polinomial de reconhecimento. Já o problema do reconhecimento dos grafos UE é NP-Completo. Consideramos também as relações de inclusão entre as classes UE e UEH e as classes UV, DV, RDV, DE, RDE, Cordal, Perfeito e Clique-Helly.