TY - JOUR
T1 - The maximum number of cliques in graphs that avoid vertex-disjoint copies of path of length two
AU - Gao, Zhipeng
AU - Li, Ping
AU - Lu, Changhong
AU - Sun, Rui
AU - Yuan, Long Tu
N1 - Publisher Copyright:
© 2025 Elsevier B.V.
PY - 2026/3
Y1 - 2026/3
N2 - 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.
AB - 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.
KW - Disjoint copies of graphs
KW - Generalized Turán number
KW - s-Cliques
UR - https://www.scopus.com/pages/publications/105022179445
U2 - 10.1016/j.disc.2025.114859
DO - 10.1016/j.disc.2025.114859
M3 - 文章
AN - SCOPUS:105022179445
SN - 0012-365X
VL - 349
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 3
M1 - 114859
ER -