Given a family of graphs <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {H},$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">H</mi> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> a graph G is <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathcal {H}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>-free if it does not contain any member of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {H}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation> as a subgraph. The generalized Turán number ex<InlineEquation ID="IEq4"> <EquationSource Format="TEX">$(n,T,\mathcal {H})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>T</mi> <mo>,</mo> <mi mathvariant="script">H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\mathcal {H}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation> is the maximum number of copies of graph T in an n-vertex <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\mathcal {H}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>-free graph. Let F be a linear forest consisting of k paths of orders <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\ell _1,\ell _2,\ldots ,\ell _k,$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ℓ</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>ℓ</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>ℓ</mi> <mi>k</mi> </msub> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> respectively. In this paper, we determine the exact value of ex<InlineEquation ID="IEq8"> <EquationSource Format="TEX">$(n,K_s,\{F,K_m\})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>K</mi> <mi>s</mi> </msub> <mo>,</mo> <mrow> <mo stretchy="false">{</mo> <mi>F</mi> <mo>,</mo> <msub> <mi>K</mi> <mi>m</mi> </msub> <mo stretchy="false">}</mo> </mrow> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for sufficiently large n under some restrictions on F and s,  and characterize the corresponding extremal graphs. Our result can be regarded as an extension of the result of Zhu and Chen (2022), and Fang, Zhu and Chen (2025), the former determined the exact value of <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\textrm{ex}(n,K_s,F)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>ex</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>K</mi> <mi>s</mi> </msub> <mo>,</mo> <mi>F</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$n=\Omega (|F|^s)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mo stretchy="false">|</mo> <mi>F</mi> <msup> <mo stretchy="false">|</mo> <mi>s</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$k\geqslant 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>⩾</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> except some <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\ell _i=3,$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ℓ</mi> <mi>i</mi> </msub> <mo>=</mo> <mn>3</mn> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> the latter determined the exact value of <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$\textrm{ex}(n,K_s,\{P_\ell ,K_m\}).$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>ex</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>K</mi> <mi>s</mi> </msub> <mo>,</mo> <mrow> <mo stretchy="false">{</mo> <msub> <mi>P</mi> <mi>ℓ</mi> </msub> <mo>,</mo> <msub> <mi>K</mi> <mi>m</mi> </msub> <mo stretchy="false">}</mo> </mrow> <mo stretchy="false">)</mo> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation>

Exact Results for Generalized Turán Number of a Linear Forest and a Clique

期刊论文
发表日期：

2026年7月20日

查看全文

Zihan Zhou,
Shuchao Li

摘要

Given a family of graphs $\mathcal {H},$ $H,$ a graph G is $\mathcal {H}$ $H$ -free if it does not contain any member of $\mathcal {H}$ $H$ as a subgraph. The generalized Turán number ex $(n,T,\mathcal {H})$ $(n, T, H)$ of $\mathcal {H}$ $H$ is the maximum number of copies of graph T in an n-vertex $\mathcal {H}$ $H$ -free graph. Let F be a linear forest consisting of k paths of orders $\ell _1,\ell _2,\ldots ,\ell _k,$ $ℓ_{1}, ℓ_{2}, \dots, ℓ_{k},$ respectively. In this paper, we determine the exact value of ex $(n,K_s,\{F,K_m\})$ $(n, K_{s}, {F, K_{m}})$ for sufficiently large n under some restrictions on F and s, and characterize the corresponding extremal graphs. Our result can be regarded as an extension of the result of Zhu and Chen (2022), and Fang, Zhu and Chen (2025), the former determined the exact value of $\textrm{ex}(n,K_s,F)$ $ex (n, K_{s}, F)$ for $n=\Omega (|F|^s)$ $n = Ω (| F |^{s})$ and $k\geqslant 2$ $k ⩾ 2$ except some $\ell _i=3,$ $ℓ_{i} = 3,$ the latter determined the exact value of $\textrm{ex}(n,K_s,\{P_\ell ,K_m\}).$ $ex (n, K_{s}, {P_{ℓ}, K_{m}}) .$