Decompositions of graphs into a given clique-extension

Sousa, Teresa. "Decompositions of graphs into a given clique-extension." Ars Combinatoria. 100 (2011): 465-472.


For r≥3, a clique-extension of order r+1 is a connected graph that consists of a Kr plus another vertex adjacent to at most r-1 vertices of Kr. 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≥3 and will also obtain all extremal graphs. This work extends results proved by Bollobás [Math.\ Proc.\ Cambridge Philosophical Soc 79 (1976) 19--24] for cliques.

Related External Link

Clique_extension.pdf103.84 KB