Extremal graphs for blow-ups of stars and paths (Q827605): Difference between revisions

Let \(H_{i}\), \(i=1,\dots,t,\) be graphs. A classical problem in the extremal graph theory asks to determine \(ex(n,H_{1},\dots,H_{t}),\) the maximum number of edges in a graph on \(n\) vertices with no subgraph \(H_{i},\) \(i=1,\dots,t\). For a graph \(G\), \(G^{p}\) (so called a blow-up graph of \(G\)) is obtained by substituting each edge of \(G\) by a clique of size \(p;\) as usual, \(P_{k}\) stands for a path on \(k\) vertices and \(S_{k}\) for a star with \(k\) edges. In the paper the number \(\operatorname{ex}(n,S_{k}^{p+1},P_{k+1}^{p+1})\) is determined for all \(k\geq 1\), \(p>2,\) and \(n\) sufficiently large.