Contagem de Conjuntos P_3-Convexos em Grafos

A convexidade P_3 é gerada pelo conjunto de todos os caminhos de três vértices de um grafo. Neste trabalho, consideramos o problema de contagem de conjuntos P_3-convexos de um grafo G. Provamos que este problema é #P-completo, mesmo para grafos split. Investigamos o problema de maximizar o número de conjuntos P_3-convexos em grafos com n vértices, caracterizando os grafos extremais (conexos ou não) que atingem a contagem máxima, igual a 2^n. Restringindo o escopo para grafos conexos, provamos que a estrela K_{1,n-1} maximiza essa contagem, estabelecendo o limite superior de 2^{n-1} + n, valor este que também é alcançado pelos caminhos P_4 e P_5. Além de caracterizar as estruturas extremais, descrevemos um algoritmo de programação dinâmica de tempo linear para árvores, demonstrando que árvores com n vértices possuem naturalmente mais conjuntos P_3-convexos que grafos com n vértices contendo ciclos. Comparamos também o crescimento exponencial da contagem em estrelas versus caminhos.