Representações para Pares Modulares de um Grafo

Um par modular num grafo $G$ é um par {Q1, Q2} de subconjuntos não-vazios de vértices de G tais que cada vértice de V(G) \ (Q1 U Q2) é adjacente a todos os vértices de Q ou não é adjacente a nenhum de seus vértices, para j=1, 2, [Q1] >= 1 e [Q2] >= 1. Neste trabalho, consideramos o problema de representar e listar os pares modulares de um grafo.

Inicialmente, mostramos uma representação para os pares modulares de um grafo, em termos de ideais de certos conjuntos parcialmente ordenados. Em seguida, utilizamos a decomposição modular, que é um tipo de decomposição em grafos, para, primeiramente, representar os pares modulares de cografos e, em seguida, apresentar um algoritmo de tempo polinomial para listar todos os pares modulares não básicos de grafos P4-esparsos (que são os grafos tais que todo conjunto de cinco vértices induz no máximo um P4) e, em particular, de grafos P4-redutíveis (que são os grafos tais que nenhum de seus vértices pertence a mais de um P4 induzido).