The maximum number of cliques in graphs that avoid vertex-disjoint copies of path of length two

Zhipeng Gao, Ping Li, Changhong Lu, Rui Sun*, Long Tu Yuan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

The problem of determining the maximum number of copies of T in an H -free graph, for any graphs T and H , was considered by Alon and Shikhelman. This is a variant of Turán's classical extremal problem. We show lower and upper bounds for the maximum number of s -cliques in a graph with no disjoint copies of an arbitrary connected graph. We also determine the maximum number of s -cliques in an n -vertex graph that does not contain a disjoint union of k paths of length two, in the cases when k=2,3, s⩾k+2, or n is sufficiently large. This result partly confirms a conjecture posed by Chen, Yang, Yuan, and Zhang.

Original languageEnglish
Article number114859
JournalDiscrete Mathematics
Volume349
Issue number3
DOIs
StatePublished - Mar 2026

Keywords

  • Disjoint copies of graphs
  • Generalized Turán number
  • s-Cliques

Fingerprint

Dive into the research topics of 'The maximum number of cliques in graphs that avoid vertex-disjoint copies of path of length two'. Together they form a unique fingerprint.

Cite this