Grafos PI

AUTOR(ES)

Sheila Morais de Almeida

DATA DE PUBLICAÇÃO

2005

RESUMO

A PI-representation consists of two parallellines, r and s, and triangles with one vertex on r and the other two on s. Let R be a PI-representation. The intersection graph of R is called PI graph when each vertex in the graph corresponds to a triangle in R and there exists an edge between two vertices if and only if their corresponding triangles intersect. According to the book Graph Classes - a Survey (1999) [3], by Brandstiidt, Le and Spinrad, the PI graph characterization and recognition problems are still open. This is the main motivation for the study of the PI graph class. In this dissertation, we present a study of PI graphs based on their relationship with other graph classes such as the interval and permutation graphs, which are well known intersection graph classes, and trapezoid graphs, which have a very similar structure to that of PI graphs. This dissertation is a survey on existing work on the PI graph class and presents new necessary andj or sufficient conditions for a graph to be PI

ASSUNTO(S)

teoria dos grafos

Documentos Relacionados

• Teoria Espectral de Grafos aplicada ao problema de Isomorfismo de Grafos
• Sobre grafos perfeitos
• Particionamento de grafos de aplicações e mapeamento em grafos de arquiteturas heterogêneas
• ANÁLISE DE AMPLITUDES DO DECAIMENTO D+ KS(PI)-(PI)+(PI)+ NO EXPERIMENTO FOCUS
• Scalar meson sigma phase motion at D+-> pi- pi+pi+ decay