<p>A digraph <i>D</i> is <i>k</i>-linked if for any pair of two disjoint vertex sets <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2970_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="117" /> </InlineMediaObject> <EquationSource Format="TEX">\(\{x_{1},x_{2},\ldots ,x_{k}\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <msub> <mi>x</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>x</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>x</mi> <mi>k</mi> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2970_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="113" /> </InlineMediaObject> <EquationSource Format="TEX">\(\{y_{1},y_{2},\ldots ,y_{k}\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <msub> <mi>y</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>y</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>y</mi> <mi>k</mi> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> in <i>D</i>, there exist vertex disjoint dipaths <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2970_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="101" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_{1},P_{2},\ldots ,P_{k}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>P</mi> <mi>k</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2970_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_{i}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> is a dipath from <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2970_Article_IEq5.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(x_{i}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>x</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> to <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2970_Article_IEq6.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(y_{i}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>y</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> for each <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2970_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">\(i\in [k]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>. Pokrovskiy (JCTB, 2015) confirmed a conjecture of Kühn et al. (Proc. Lond. Math. Soc., 2014) by verifying that every 452<i>k</i>-connected tournament is <i>k</i>-linked. Meng et al. (Eur. J. Comb., 2021) improved this upper bound by showing that any <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2970_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">\((40k-31)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>40</mn> <mi>k</mi> <mo>-</mo> <mn>31</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-connected tournament is <i>k</i>-linked. In this paper, we show a better upper bound by proving that every <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2970_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="88" /> </InlineMediaObject> <EquationSource Format="TEX">\(\lceil 12.5k-6\rceil \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>⌈</mo> <mn>12.5</mn> <mi>k</mi> <mo>-</mo> <mn>6</mn> <mo>⌉</mo> </mrow> </math></EquationSource> </InlineEquation>-connected tournament with minimum out-degree at least <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2970_Article_IEq10.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="64" /> </InlineMediaObject> <EquationSource Format="TEX">\(21k-14\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>21</mn> <mi>k</mi> <mo>-</mo> <mn>14</mn> </mrow> </math></EquationSource> </InlineEquation> is <i>k</i>-linked. Furthermore, we improve a key lemma that was first introduced by Pokrovskiy (JCTB, 2015) and later enhanced by Meng et al. (Eur. J. Comb., 2021).</p>

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

A New Connectivity Bound for a Tournament to be Highly Linked

  • Bin Chen,
  • Xinmin Hou,
  • Gexin Yu,
  • Xinyu Zhou

摘要

A digraph D is k-linked if for any pair of two disjoint vertex sets \(\{x_{1},x_{2},\ldots ,x_{k}\}\) { x 1 , x 2 , , x k } and \(\{y_{1},y_{2},\ldots ,y_{k}\}\) { y 1 , y 2 , , y k } in D, there exist vertex disjoint dipaths \(P_{1},P_{2},\ldots ,P_{k}\) P 1 , P 2 , , P k such that \(P_{i}\) P i is a dipath from \(x_{i}\) x i to \(y_{i}\) y i for each \(i\in [k]\) i [ k ] . Pokrovskiy (JCTB, 2015) confirmed a conjecture of Kühn et al. (Proc. Lond. Math. Soc., 2014) by verifying that every 452k-connected tournament is k-linked. Meng et al. (Eur. J. Comb., 2021) improved this upper bound by showing that any \((40k-31)\) ( 40 k - 31 ) -connected tournament is k-linked. In this paper, we show a better upper bound by proving that every \(\lceil 12.5k-6\rceil \) 12.5 k - 6 -connected tournament with minimum out-degree at least \(21k-14\) 21 k - 14 is k-linked. Furthermore, we improve a key lemma that was first introduced by Pokrovskiy (JCTB, 2015) and later enhanced by Meng et al. (Eur. J. Comb., 2021).