2025/08/28 by Adak, Rajat, Chandran, L. Sunil · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.20936
Let F be a family of graphs. A graph is called F-free if it does not contain any member of F. Generalized Turán problems aim to maximize the number of copies of a graph H in an n-vertex F-free graph. This maximum is denoted by ex(n, H, F). When H ≅ K2, it is simply denoted by ex(n,F). Erdős and Gallai established the bounds ex(n, Pk+1) ≤ (n(k-1))/(2) and ex(n, C≥ k+1) ≤ (k(n-1))/(2). This was later extended by Luo \citeluo2018maximum, who showed that ex(n, Ks, Pk+1) ≤ (n)/(k) \binomks and ex(n, Ks, C≥ k+1) ≤ (n-1)/(k-1) \binomks. Let N(G,Ks) denote the number of copies of Ks in G. In this paper, we use the vertex-based localization framework, introduced in \citeadak2025vertex, to generalize Luo's bounds. In a graph G, for each v ∈ V(G), define p(v) to be the length of the longest path that contains v. We show that N(G,Ks) ≤ ∑v ∈ V(G) (1)/(p(v)+1)p(v)+1\choose s = (1)/(s)∑v ∈ V(G)p(v) \choose s-1 We strengthen the cycle bound from \citeluo2018maximum as follows: In graph G, for each v ∈ V(G), let c(v) be the length of the longest cycle that contains v, or 2 if v is not part of any cycle. We prove that N(G,Ks) ≤ (∑v∈ V(G)(1)/(c(v)-1)c(v) \choose s) - (1)/(c(u)-1)c(u) \choose s where c(u) denotes the circumference of G. Furthermore, we characterize the class of extremal graphs that attain equality for these bounds. We provide full proofs for the cases s = 1 and s ≥ 3, while the case s = 2 follows from the result in \citeadak2025vertex. We also conclude with a generalization of a result by Balister-Bollobás-Riordan-Schelp \citeBALISTER2003366.