Decomposições Mínimas de Grafos - Alguns resultados exactos

Dados dois grafos G e H, uma H-decomposição do grafo G é uma partição das suas arestas de modo que cada parte seja ou uma aresta ou um grafo isomorfo a H. Denote-se por f(H; n) o menor número q de modo a que qualquer grafo G com n vértices admita uma H-decomposição com um máximo de q elementos. Dado H, o valor exacto da função f(H; n) é ainda um problema em aberto. Erdös, Goodman e Pósa (1966) determinaram f(K3; n), onde Kr denota o grafo completo (clique) com r vértices. Este resultado foi extendido por Bollobás (1976) ao determinar f(Kr;n), para todo o r maior ou igual a 4. Nesta palestra apresenta-se o valor exacto da função f(H; n) nos casos em que H é uma extensão de clique, C5 e C5 + e.