The maximum number of triangles in graphs without the square of a path
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912824004968448 |
|---|---|
| author | Wang, Yichen Győri, Ervin |
| author_facet | Wang, Yichen Győri, Ervin |
| contents | The generalized Turán number for $H$ of $G$, denoted by $\ex(n,H,G)$, is the maximum number of copies of $H$ in an $n$-vertex $G$-free graph. When $H$ is an edge, $\ex(n,H,G)$ is the classical Turán number $\ex(n,G)$. Let $P_k$ be the path with $k$ vertices. The square of $P_k$, denoted by $P_k^2$, is obtained by joining the pairs of vertices with distance at most two in $P_k$.
The Turán number of $P_k^2$, $\ex(n, P_k^2)$, was determined by several researchers. When $k=3$, $P_3^2$ is the triangle and $\ex(n, P_3^2)$ is well-known from Mantel's theorem. When $k=4$, $\ex(n, P_4^2)$ was solved by Dirac in a more general context. When $k=5,6$, the problem was solved by Xiao, Katona, Xiao, and Zamora. For general $k \ge 7$, the problem was solved by Yuan in a more general context.
Recently, Mukherjee determined the generalized Turán number $\ex(n, K_3, P_5^2)$. In this paper, we determine the exact value of $\ex(n, K_3, P_6^2)$ and characterize all the extremal graphs for $n \ge 11$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_09454 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The maximum number of triangles in graphs without the square of a path Wang, Yichen Győri, Ervin Combinatorics The generalized Turán number for $H$ of $G$, denoted by $\ex(n,H,G)$, is the maximum number of copies of $H$ in an $n$-vertex $G$-free graph. When $H$ is an edge, $\ex(n,H,G)$ is the classical Turán number $\ex(n,G)$. Let $P_k$ be the path with $k$ vertices. The square of $P_k$, denoted by $P_k^2$, is obtained by joining the pairs of vertices with distance at most two in $P_k$. The Turán number of $P_k^2$, $\ex(n, P_k^2)$, was determined by several researchers. When $k=3$, $P_3^2$ is the triangle and $\ex(n, P_3^2)$ is well-known from Mantel's theorem. When $k=4$, $\ex(n, P_4^2)$ was solved by Dirac in a more general context. When $k=5,6$, the problem was solved by Xiao, Katona, Xiao, and Zamora. For general $k \ge 7$, the problem was solved by Yuan in a more general context. Recently, Mukherjee determined the generalized Turán number $\ex(n, K_3, P_5^2)$. In this paper, we determine the exact value of $\ex(n, K_3, P_6^2)$ and characterize all the extremal graphs for $n \ge 11$. |
| title | The maximum number of triangles in graphs without the square of a path |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2601.09454 |