Metraipolis › archive › dc_43f4213be4cd

The strong (non-induced) Turán numbers — arXiv:2609.29304

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.29304
License (as archived)
CC0-1.0
Archived
2026-10-08T06:36:44.353Z
SHA-256 of the archived text
4065d88c6d22bce358cf524e14964fb0623ec9e4961575437841c972cfc3747b
Stable URL of this page
https://metraipolis.com/documento/dc_43f4213be4cd

How to cite

The strong (non-induced) Turán numbers — arXiv:2609.29304 — arXiv (en), https://arxiv.org/abs/2609.29304 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_43f4213be4cd (Metraipolis archive dc_43f4213be4cd, sha256 4065d88c6d22bce358cf524e14964fb0623ec9e4961575437841c972cfc3747b)
BibTeX
@misc{dc43f4213be4cd,
  title = {The strong (non-induced) Turán numbers — arXiv:2609.29304},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.29304},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_43f4213be4cd; sha256 4065d88c6d22bce358cf524e14964fb0623ec9e4961575437841c972cfc3747b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.29304. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In this paper we introduce and explore the following new graph invariant: For a graph $G$ on $k$ vertices, $G \neq 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) \leq st(n,G) = ex(n, D(G) ) \leq \min \{ ex(n,H) : H \in D(G) \}$ holds for all $n \geq |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) \geq 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\geq 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 \geq 2$ and $q \geq k+1 \geq 3$, then $ex(n, \{C_3,...,C_{k+1}\}) \leq st(n,T) \leq 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^* \cup tK_1$ are obtained, moreover the value of $st(n,G)$ is computed for all graphs on at most 4 vertices.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.29304 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T06:02:10.030Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).