$H$-Decompositions of $r$-graphs when $H$ is an $r$-graph with exactly 2 edges

Teresa Sousa

Abstract


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 is either a single edge or forms a graph isomorphic to $H$. The minimum number of parts in an $H$-decomposition of $G$ is denoted by $\phi_H^r (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 case 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 $\phi_H^r(n)$ will be obtained for bowtie, domino and kite decompositons of $r$-graphs.


Full Text: PDF