Extremal Graphs for Blow-Ups of Keyrings
2020
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\ge 3$$
,
$$s\ge 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).
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
2
Citations
NaN
KQI