Teresa Maria Jerónimo Sousa

A graph that consists of t cliques sharing a vertex v is said to be a t-friendship graph with center v. A friendship graph is a graph that is t-friendship for some . We solve the problem of finding the best upper bound for the size of a greedy 2-friendship decomposition and a greedy friendship decomposition of graphs of order n.

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.

The concept of H-decompositions of graphs was first introduced by Erdös, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. 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 Ф(n,H) be the smallest number Ф, such that, any graph of order n admits an H-decomposition with at most Ф parts. The exact computation of Ф(n,H) for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decompositions of graphs.

Let G be a simple graph. A clique is a subgraph of G isomorphic to a complete graph, and a t-friendship graph is a graph consisting of t edge-disjoint cliques sharing one vertex. A t-friendship decomposition of G for a fixed value of t is a set F of edge-disjoint t-friendship subgraphs of G such that every edge of G belongs to exactly one element of F. It is proved that any graph of order n admits a t-friendship decomposition with at most n2/4t+n/4t+n elements for all fixed t≥2. For t=2,3 exact bounds are given. For t=2 the bound is ⌈n2/8⌉ for n even and (n2−1)/8 for n odd; for t=3 the bound is ⌈n2/12⌉ for n even and ⌈(n2−1)/12⌉ for n odd.

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.

In this paper we consider the problem of finding the smallest number such that any graph G of order n admits a decomposition into edge disjoint copies of C_4 and single edges with at most elements. We solve this problem for n sufficiently large.

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.

Given graphs G and H and a positive number b, a weighted (H,b)-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms an H-subgraph. We assign a weight of b to each H-subgraph in the decomposition and a weight of 1 to single edges. The total weight of the decomposition is the sum of the weights of all elements in the decomposition. Let f(n,H,b) be the the smallest number such that any graph G of order n admits an (H,b)-decomposition with weight at most f(n,H,b). The value of the function f(n,H,b) when b=1 was determined, for large n, by Pikhurko and Sousa [Pikhurko, O. and Sousa, T., Minimum H-Decompositions of Graphs, Journal of Combinatorial Theory, B, 97 (2007), 1041--1055.Here we determine the asymptotic value of f(n,H,b)for any fixed bipartite graph H and any value of b as n tends to infinity.

A friendship graph is a graph consisting of cliques sharing a common vertex. In this paper we investigate the maximum number of elements in an optimal friendship decomposition of graphs of order n. We obtain upper and lower bounds for this number. These bounds relate this problem with the classical Ramsey numbers.

"Given two r-graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part either is a single edge or forms a graph isomorphic to H. The minimum number of parts in an H-decomposition of G is denoted by φrH(G). By a 2-edge-decomposition of an r-graph we mean an H-decomposition for any fixed r-graph H with exactly 2 edges. In the special cases where the two edges of H intersect in exactly 1, 2 or r−1 vertices, these 2-edge-decompositions will be called bowtie, domino and kite, respectively. The value of the function φrH(n) will be obtained for bowtie, domino and kite decompositions of r-graphs.''