Teresa Maria Jerónimo Sousa

If H is a family of graphs, then an H-decomposition of a graph G is a partition of the edges of G each element of which induces a copy of a graph in G.
This paper addresses the problem of finding the number φ(n,H), the smallest number k such that every graph on n vertices has an H-decomposition with at most k elements. φ(n,H) is found in the cases when H={K2,C5}; when H={K2,C5+e}, where e is a chord of the C5; when H={K2,K4−e}; and when H={K2,K3+e}, where e is a pendant edge added to one vertex in the K3.

For r≥3, a clique-extension of order r+1 is a connected graph that consists of a Kr plus another vertex adjacent to at most r-1 vertices of Kr. In this paper we consider the problem of finding the smallest number t such that any graph G of order n admits a decomposition into edge disjoint copies of a fixed graph H and single edges with at most t elements. Here we solve the case when H is a fixed clique-extension of order r+1, for all r≥3 and will also obtain all extremal graphs. This work extends results proved by Bollobás [Math.\ Proc.\ Cambridge Philosophical Soc 79 (1976) 19--24] for cliques.

Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let f_H(n) be the smallest number t such that any graph G of order n admits an H-decomposition with at most t parts. Here we study the case when H=C_7, that is, the cycle of length 7 and prove that f_{C_7}(n)=\lfloor n^2/4 \rfloor for all n≥10.