Decompositions of Graphs into a Given Clique-Extension

Abstract

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\). 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 \geq 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.