Exact generalized Turán number for $K_3$ versus suspension of $P_4$
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917563642937344 |
|---|---|
| author | Mukherjee, Sayan |
| author_facet | Mukherjee, Sayan |
| contents | Let $P_4$ denote the path graph on $4$ vertices. The suspension of $P_4$, denoted by $\widehat P_4$, is the graph obtained via adding an extra vertex and joining it to all four vertices of $P_4$. In this note, we demonstrate that for $n\ge 8$, the maximum number of triangles in any $n$-vertex graph not containing $\widehat P_4$ is $\left\lfloor n^2/8\right\rfloor$. Our method uses simple induction along with computer programming to prove a base case of the induction hypothesis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_04369 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Exact generalized Turán number for $K_3$ versus suspension of $P_4$ Mukherjee, Sayan Combinatorics 05C35 Let $P_4$ denote the path graph on $4$ vertices. The suspension of $P_4$, denoted by $\widehat P_4$, is the graph obtained via adding an extra vertex and joining it to all four vertices of $P_4$. In this note, we demonstrate that for $n\ge 8$, the maximum number of triangles in any $n$-vertex graph not containing $\widehat P_4$ is $\left\lfloor n^2/8\right\rfloor$. Our method uses simple induction along with computer programming to prove a base case of the induction hypothesis. |
| title | Exact generalized Turán number for $K_3$ versus suspension of $P_4$ |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2307.04369 |