Extremal Graphs for Blow-Ups of Keyrings

The blow-up of a graph H is the graph obtained from replacing each edge in H by a clique of the same size where the new vertices of the cliques are all different. Given a graph H and a positive integer n, the extremal number, ex(n, H), is the maximum number of edges in a graph on n vertices that does not contain H as a subgraph. A keyring C-s(k) is a (k + s)-edge graph obtained from a cycle of length k by appending s leaves to one of its vertices. This paper determines the extremal number and finds the extremal graphs for the blow-ups of keyrings C-s(k) (k >= 3, s >= 1) when n is sufficiently large. For special cases when k = 0 or s = 0, the extremal number of the blow-ups of the graph C-s(0) (a star) has been determined by Erdos et al. (J Comb Theory Ser B 64:89-100, 1995) and Chen et al. (J Comb Theory Ser B 89: 159-171, 2003), while the extremal number and extremal graphs for the blow-ups of the graph C-0(k) (a cycle) when n is sufficiently large has been determined by Liu (Electron J Combin 20: P65, 2013).