The strong (non-induced) Tur\'an numbers

In this paper we introduce and explore the following new graph invariant: For a graph $G$ on $k$ vertices, $G\ne K_k$, let $st(n,G)$ denote the maximum number of edges in a graph of order $n$ which does not contain any subgraph on $k$ vertices strictly containing $G$. A basic relation to classical Tur\'an numbers is developed via the following: For $G$ on $k$ vertices, let $D(G)=\{H:|H|=|G|,H=G+e\}$. Using this notion we prove that $ex(n,G)\le st(n,G)=ex(n,D(G))\le \min \{ex(n,H):H\in D(G)\}$ holds for all $n\ge |G|$. The family $D(G)$ happened to be smoothly amenable to the use of classical extremal results, and in many cases allows us to get asymptotically sharp estimates as well as exact values of $st(n,G)$. From the many results proved here we state the following as an illustration. (1) If $\chi (G)\ge 3$ and $\chi (D(G))=\chi (G)$, then $st(n,G)=(1+o(1))ex(n,K_{\chi (G)})$. (2) If $\chi (D(G))=\chi (G)+1$, then $G$ is a complete $\chi (G)$-partite graph and $st(n,G)=ex(n,K_{\chi (G)+1})$ for $n$ sufficiently large. (3) For $k$ odd, $k\ge 5$, $st(n,C_k)=ex(n,C_k)=ex(n,K_3)$ for $n$ sufficiently large. (4) If $T$ is a tree of order $q$ with diameter $k\ge 2$ and $q\ge k+1\ge 3$, then $ex(n,\{C_3,...,C_{k+1}\})\le st(n,T)\le ex(n,\{C_3,...,C_{k+1}\})+(q-1)n$. Many results concerning even cycles, theta graphs, dense bipartite graphs and graphs of the form $G=G^{\ast }\cup t{K}_1$ are obtained, moreover the value of $st(n,G)$ is computed for all graphs on at most 4 vertices.