Extremal Graphs for Blow-Ups of Keyrings
- PDF / 1,095,355 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 67 Downloads / 161 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Extremal Graphs for Blow-Ups of Keyrings Zhenyu Ni1 • Liying Kang1
•
Erfang Shan2 • Hui Zhu1
Received: 21 November 2019 / Revised: 18 May 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract 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 Cs ð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 Cs ð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 Cs ð0Þ (a star) has been determined by Erdo¨s 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 C0 ðkÞ (a cycle) when n is sufficiently large has been determined by Liu (Electron J Combin 20: P65, 2013). Keywords Extremal graph Tura´n graph Intersecting clique Keyring Blow-up
Mathematics Subject Classification 05C35
Research was partially supported by NSFC (Grant numbers 11971298, 11871329). & Liying Kang [email protected] Zhenyu Ni [email protected] Erfang Shan [email protected] Hui Zhu [email protected] 1
Department of Mathematics, Shanghai University, Shanghai 200444, People’s Republic of China
2
School of Management, Shanghai University, Shanghai 200444, People’s Republic of China
123
Graphs and Combinatorics
1 Introduction In this paper, all graphs considered are undirected graphs without loops and multiple edges. For a graph G, denote by E(G) the set of edges and V(G) the set of vertices of G. We denote the number of edges in G by eðGÞ ¼ jEðGÞj. As usual, Pn , Cn and Kn denote a path, a cycle and a complete graph on n vertices, respectively; Ki;j (i; j 2 N) denotes the complete bipartite graph with parts of cardinality i and j. The graph K3 ¼ C3 is also called a triangle, K1;j (j 2) a star, denoted by Sj for convenience. For a graph G and a vertex v 2 VðGÞ, the neighborhood of v in G is denoted by NG ðvÞ ¼ fu 2 VðGÞ : uv 2 EðGÞg, and the closed neighborhood NG ½v of v is NG ðvÞ [ fvg. The degree of the vertex v, written as dG ðvÞ or simply d(v), is the number of edges incident with v, that is, dG ðvÞ ¼ jNG ðvÞj. A vertex of degree zero is called an isolated vertex. A vertex of degree k is called a degree-k vertex. The maximum and minimum degrees of G are denoted by DðGÞ and dðGÞ, respectively. A matching in G is a set of vertex disjoint edges from E(G), and denoted by Mk a matching of size k. The maximum number of edges in a matching of a graph G is called the matching number of G and denoted by mðGÞ. A (vertex) cover of G is
Data Loading...
