Teresa Maria Jeronimo Sousa
“Decompositions of Graphs”
Thursday, February 9, 2006
4:00 p.m.
Posner Hall, Room 259
ABSTRACT:
The subject of graph decompositions is a vast topic and has been studied for the past 40 years by numerous people. 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$. We allow partitions only, that is, every edge of $G$ appears in precisely one part. Let $\phi_H(G)$ be the smallest possible number of parts in an $H$-decomposition of $G$. We study the function $\phi_H(n)$ which is the smallest number such that any graph $G$ of order $n$ admits an $H$-decomposition with at most $\phi_H(n)$ elements.
Erdos, Goodman and Posa proved that $\phi_{K_{3}}(n)=t_2(n)$, where $t_{r-1}(n)$ denotes the number of edges in the Turan Graph, $T_{r-1}(n)$. This result was extended by Bollobas, who proved that $\phi_{K_{r}}(n)=t_{r-1}(n)$, for all $n \geq r \geq 3$.
We managed to obtain the exact value of $\phi_H(n)$ for some graphs $H$, namely the cycle of length 5, the cycle of length 5 with one chord and any clique-extension of order $r+1$. For $r \geq 3$ a clique-extension of order $r+1$ is a connected graph that consists of a $K_r$ plus another vertex adjacent to at most $r-1$ vertices of $K_r$. For all fixed $H$ with chromatic number $r \geq 3$ we will prove an asymptotic result about $\phi_H(n)$, that is we show that $\phi_H(n)= t_{r-1}(n)+o(n^2)$. For a non-empty graph $H$ we denote by gcd(H) the greatest common divisor of the degrees of $H$. For a bipartite graph with gcd(H)=1 the exact value of the function $\phi_H(n)$ will be obtained, for $n$ sufficiently large.
The proofs presented use Turan’s Theorem, the Regularity Lemma, results of Pippenger and Spencer, Gustavsson’s Decomposition Theorem for dense graphs and results about packing vertex disjoint copies of a fixed graph $H$ into a large graph $G$.
This is joint work with Oleg Pikhurko.
