<p>A graph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(H\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>H</mi> </math></EquationSource> </InlineEquation>-free if <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation> contains no copy of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(H\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>H</mi> </math></EquationSource> </InlineEquation> as a subgraph. The Turán number of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(H\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>H</mi> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="63" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{ex}(n, H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>ex</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, is the maximum number of edges over all <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq7.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(H\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>H</mi> </math></EquationSource> </InlineEquation>-free graphs on <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq8.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation> vertices. Let <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{EX}(n, H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>EX</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> be the collection of all <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq10.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(H\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>H</mi> </math></EquationSource> </InlineEquation>-free graphs on <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq11.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation> vertices with <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq12.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="63" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{ex}(n, H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>ex</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> edges. Recently, Chen et al. determined the value of <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq13.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="91" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{ex}(n, 2K_{p+ 1})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>ex</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>2</mn> <msub> <mi>K</mi> <mrow> <mi>p</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Zhang and also Zhang and Yin determined the value of <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq14.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="91" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{ex}(n, 3K_{p+ 1})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>ex</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>3</mn> <msub> <mi>K</mi> <mrow> <mi>p</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Hu determined the value of <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq15.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="123" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{ex}(n, K_{p+ 1}\cup K_{q})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>ex</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>K</mi> <mrow> <mi>p</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>∪</mo> <msub> <mi>K</mi> <mi>q</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for all <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq16.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(p\ge q\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>≥</mo> <mi>q</mi> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we characterize <InlineEquation ID="IEq17"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq17.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="130" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{EX}(n, K_{p+ 1}\cup K_{q})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>EX</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>K</mi> <mrow> <mi>p</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>∪</mo> <msub> <mi>K</mi> <mi>q</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for all <InlineEquation ID="IEq18"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2914_Article_IEq18.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(p\ge q\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>≥</mo> <mi>q</mi> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Extremal Graphs for the Union of Two Vertex-Disjoint Cliques

  • Zhidan Luo

摘要

A graph \(G\) G is \(H\) H -free if \(G\) G contains no copy of \(H\) H as a subgraph. The Turán number of \(H\) H , \(\textrm{ex}(n, H)\) ex ( n , H ) , is the maximum number of edges over all \(H\) H -free graphs on \(n\) n vertices. Let \(\textrm{EX}(n, H)\) EX ( n , H ) be the collection of all \(H\) H -free graphs on \(n\) n vertices with \(\textrm{ex}(n, H)\) ex ( n , H ) edges. Recently, Chen et al. determined the value of \(\textrm{ex}(n, 2K_{p+ 1})\) ex ( n , 2 K p + 1 ) . Zhang and also Zhang and Yin determined the value of \(\textrm{ex}(n, 3K_{p+ 1})\) ex ( n , 3 K p + 1 ) . Hu determined the value of \(\textrm{ex}(n, K_{p+ 1}\cup K_{q})\) ex ( n , K p + 1 K q ) for all \(p\ge q\) p q . In this paper, we characterize \(\textrm{EX}(n, K_{p+ 1}\cup K_{q})\) EX ( n , K p + 1 K q ) for all \(p\ge q\) p q .