Decompositions of Graphs into a Given Clique-Extension

Abstract

For $r\ge 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$. 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 $\tau$ elements. Here, we solve the case when $H$ is a fixed clique-extension of order $r+1$, for all $r\ge 3$, and will also obtain all extremal graphs. This work extends results proved by Bollobás [Math. Proc. Cambridge Philos. Soc. $79(1976)19-24]$ for cliques.