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.

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 φH(n) be the smallest number φ such that every graph G of order n admits an H-decomposition with at most φ parts. In the paper it is proved that φH(n)=tr−1(n)+o(n2) for every graph H of chromatic number r≥3, where tr(n) is the maximum size of an r-partite graph of order n. Moreover, when H is bipartite, the authors determine φH(n) with a constant additive error.

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.

"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.''

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.

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 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.

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.

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.

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 k be a positive integer and G be a k-connected graph. An edge-coloured path is rainbow if its edges have distinct colours. The rainbow k-connection number of G, denoted by rc_k(G), is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by k internally vertex-disjoint rainbow paths. The function rc_k(G) was first introduced by Chartrand, Johns, McKeon, and Zhang in 2009, and has since attracted considerable interest. In this paper, we consider a version of the function rc_k(G) which involves vertex-colourings. A vertex-coloured path is vertex-rainbow if its internal vertices have distinct colours. The rainbow vertex k-connection number of G, denoted by rvc_k(G), is the minimum number of colours required to colour the vertices of G so that any two vertices of G are connected by k internally vertex-disjoint vertex-rainbow paths. We shall study the function rvc_k(G) when G is a cycle, a wheel, and a complete multipartite graph. We also construct graphs G where rc_k(G) is much larger than rvc_k(G) and vice versa so that we cannot in general bound one of rc_k(G) and rvc_k(G) in terms of the other.

Given graphs G and H, and a coloring of the edges of G with k colors, a monochromatic 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 monochromatic graph isomorphic to H. Let f_{k}(n,H) be the smallest number t such that any k-edge-colored graph G of order n, admits a monochromatic H-decomposition with at most t parts. Here we study the function f_{k}(n,K_r) for k ≥2 and r≥ 3.

Given graphs G and H, and a coloring of the edges of G with k colors, a monochromatic 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 monochromatic graph isomorphic to H. Let f_{k}(n,H) be the smallest number t such that any graph G of order n and any coloring of its edges with k colors, admits a monochromatic H-decomposition with at most t parts. Here we study the function f_{k}(n,K_r) for k≥ 2 and r≥ 3.

An edge-coloured path is rainbow if its edges have distinct colours. The rainbow connection number of a connected graph G, denoted by rc(G), is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by a rainbow path. The function rc(G) was first introduced by Chartrand et al.~[Math.~Bohem., 133(1) (2008), pp.85-98], and has since attracted considerable interest. In this paper, we introduce two extensions of the rainbow connection number to hypergraphs. We study these two extensions of the rainbow connection number in minimally connected hypergraphs, hypergraph cycles and complete multipartite hypergraphs.

Let k be a positive integer and G be a k-connected graph. In 2009, Chartrand, Johns, McKeon, and Zhang introduced the rainbow k-connection number rc_k(G) of G. An edge-coloured path is rainbow if its edges have distinct colours. Then, rc_k(G) is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by k internally vertex-disjoint rainbow paths. The function rc_k(G) has since been studied by numerous researchers. An analogue of the function rc_k(G) involving vertex colourings, the rainbow vertex k-connection number rvc_k(G), was subsequently introduced. In this paper, we introduce a version which involves total colourings. A total-coloured path is total-rainbow if its edges and internal vertices have distinct colours. The total rainbow k-connection number of G, denoted by trc_k(G), is the minimum number of colours required to colour the edges and vertices of $G$, so that any two vertices of $G$ are connected by $k$ internally vertex-disjoint total-rainbow paths. We study the function trc_k(G) when G is a cycle, a wheel, and a complete multipartite graph. We also compare the functions rc_k(G), rvc_k(G), and trc_k(G), by considering how close and how far apart trc_k(G) can be from rc_k(G) and rvc_k(G).

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.

Let $G$ be a graph whose edges are coloured with $k$ colours, and $\mathcal H=(H_1,\dots , H_k)$ be a $k$-tuple of graphs. A \emph{monochromatic $\mathcal 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 monochromatic copy of $H_i$ in colour $i$, for some $1\le i\le k$. Let $\phi_{k}(n,\mathcal H)$ be the smallest number $\phi$, such that, for every
order-$n$ graph and every $k$-edge-colouring, there is a monochromatic $\mathcal H$-decomposition with at most $\phi$ elements. Extending the previous results of Liu and Sousa [``Monochromatic $K_r$-decompositions of graphs", \emph{Journal of Graph Theory}76:89-100,2014], we solve this problem
when each graph in $\mathcal H$ is a clique and $n\ge n_0(\mathcal H)$ is sufficiently large.

Given two 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(n;H) be the smallest number  such that any graph
G of order n admits an H-decomposition with at most f(n;H)  parts. Pikhurko and
Sousa conjectured that f(n;H) = ex(n;H) for (H)  3 and all sufficiently
large n, where ex(n;H) denotes the maximum number of edges in a graph on n vertices not containing H as a subgraph. Their conjecture has been veried by
Ozkahya and Person for all edge-critical graphs H. In this article, the conjecture
is veried for the k-fan graph. The k-fan graph, denoted by F_k, is the graph on
2k + 1 vertices consisting of k triangles which intersect in exactly one common
vertex called the centre of the k-fan.