Decompositions of graphs into a given clique-extension

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


For $r\geq 3$, a \emph{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 $t$ 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\'as~[Math.\ Proc.\ Cambridge Philosophical Soc.\ \textbf{79} (1976) 19--24] for cliques.
Original languageUnknown
Pages (from-to)465-472
JournalARS Combinatoria
Issue number1
Publication statusPublished - 1 Jan 2011

Cite this