Decompositions of graphs into a given clique-extension
- Citation:
- Sousa, Teresa. "Decompositions of graphs into a given clique-extension." Ars Combinatoria. 100 (2011): 465-472.
Abstract:
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.
