Teresa Maria Jerónimo Sousa

Citation:

Liu, H., and Teresa Sousa. "Fan Decompositions of Graphs." Journal of Graph Theory (In Press).

Abstract:

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.