Exact generalized Turan number for $K_3$ versus suspension of $P_4$

Published in Discrete Mathematics Vol. 347 (4), 2024

Recommended citation: Mukherjee, Sayan. "Exact generalized Turan number for $K_3$ versus suspension of $P_4$". Discrete Mathematics 347 (4) https://doi.org/10.1016/j.disc.2023.113866

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.

Download paper here

Author’s Personalized Share Link (valid for download till 2024/02/29)

Repository with companion code