The strong (non-induced) Turán numbers
Abstract
In this paper we introduce and explore the following new graph invariant: For a graph G on k vertices, G ≠ Kk, 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án 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) ≤ st(n,G) = ex(n, D(G) ) ≤ min { ex(n,H) : H ∈ D(G) } holds for all n ≥ |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 χ(G) ≥ 3 and χ(D(G)) = χ(G), then st(n,G) = (1+o(1))ex(n,Kχ(G)). (2) If χ(D(G)) = χ(G) +1, then G is a complete χ(G)-partite graph and st(n,G) = ex(n,Kχ(G) +1) for n sufficiently large. (3) For k odd, k≥ 5, st(n,Ck) = ex(n,Ck) = ex(n,K3) for n sufficiently large. (4) If T is a tree of order q with diameter k ≥ 2 and q ≥ k+1 ≥ 3, then ex(n, {C3,...,Ck+1}) ≤ st(n,T) ≤ ex(n, {C3,...,Ck+1}) + (q−1)n. Many results concerning even cycles, theta graphs, dense bipartite graphs and graphs of the form G = G* ∪ tK1 are obtained, moreover the value of st(n,G) is computed for all graphs on at most 4 vertices.
Related
BibTeX
@misc{caro2026strong,
title = {{The strong (non-induced) Turán numbers}},
author = {Yair Caro and Zsolt Tuza},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29304},
eprint = {2609.29304},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29304},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The strong (non-induced) Turán numbers
AU - Yair Caro
AU - Zsolt Tuza
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.29304
UR - https://arxiv.org/abs/2609.29304
AB - In this paper we introduce and explore the following new graph invariant: For a graph G on k vertices, G ≠ 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án 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) ≤ st(n,G) = ex(n, D(G) ) ≤ min { ex(n,H) : H ∈ D(G) } holds for all n ≥ |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 χ(G) ≥ 3 and χ(D(G)) = χ(G), then st(n,G) = (1+o(1))ex(n,K_χ(G)). (2) If χ(D(G)) = χ(G) +1, then G is a complete χ(G)-partite graph and st(n,G) = ex(n,K_χ(G) +1) for n sufficiently large. (3) For k odd, k≥ 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 ≥ 2 and q ≥ k+1 ≥ 3, then ex(n, {C_3,...,C_k+1}) ≤ st(n,T) ≤ 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^* ∪ tK_1 are obtained, moreover the value of st(n,G) is computed for all graphs on at most 4 vertices.
ER -