Counting triangles in graphs without suspensions of paths

Abstract

For a graph H, the suspension Ĥ of H is a graph obtained from H by joining a new vertex to every vertex of H. The generalized Turán number ex(n,K₃,Ĥ) is the maximum number of triangles in an n-vertex Ĥ-free graph. For fixed k ≥ 4, Mubayi and Mukherjee conjectured that ex(n,K₃,P̂_k) =⌊(k−2)/2⌋n²/8+o(n²), as n → ∞, where P_k is the path on k vertices. They verified the conjecture for k=4,5,6. In this paper, we determine the asymptotic value of ex(n,K₃,P̂_k) for every k≥ 4 via a unified approach and thus prove the conjecture of Mubayi and Mukherjee.

Turán numbers for suspensions of bipartite 2-regular graphs
Haoxing Wu, Junxue Zhang
arXiv29 Oct 2026PreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
High-chromatic tournament parts without a complete pair of cyclic triangles
Guantao Chen, Hein van der Holst, Shengze Wang
arXiv27 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
On the maximum number of triangles in tripartite graphs with no $4$-cycles between any two parts
Chunqiu Fang, Rongxing Xu
arXiv6 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Ordered matchings versus triangles via pseudorandom triangle-free graphs
Wen Chen, Qizhong Lin, Chunlin You
arXiv17 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
The maximum number of triangles in regular graphs
Ya-Hong Chen, Shi-Cai Gong, Changhong Lu +2
arXiv29 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{dou2026counting,
  title = {{Counting triangles in graphs without suspensions of paths}},
  author = {Chunyang Dou and Xing Peng},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.17839},
  eprint = {2610.17839},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.17839},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Counting triangles in graphs without suspensions of paths
AU  - Chunyang Dou
AU  - Xing Peng
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.17839
UR  - https://arxiv.org/abs/2610.17839
AB  - For a graph H, the suspension Ĥ of H is a graph obtained from H by joining a new vertex to every vertex of H. The generalized Turán number ex(n,K_3,Ĥ) is the maximum number of triangles in an n-vertex Ĥ-free graph. For fixed k ≥ 4, Mubayi and Mukherjee conjectured that ex(n,K_3,P̂_k) =⌊(k−2)/2⌋n^2/8+o(n^2), as n → ∞, where P_k is the path on k vertices. They verified the conjecture for k=4,5,6. In this paper, we determine the asymptotic value of ex(n,K_3,P̂_k) for every k≥ 4 via a unified approach and thus prove the conjecture of Mubayi and Mukherjee.
ER  -

Abstract

Related

Cite