Scholarlink

<p>The <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\((n-\ell )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mi>ℓ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation><i>-deck</i> of an <i>n</i>-vertex graph is the multiset of (unlabeled) subgraphs obtained from it by deleting <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation> vertices. An <i>n</i>-vertex graph is <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation><i>-reconstructible</i> if it is determined by its <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\((n-\ell )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mi>ℓ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-deck, meaning that no other graph has the same deck. We prove that every tree with at least <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(6\ell +11\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>6</mn> <mi>ℓ</mi> <mo>+</mo> <mn>11</mn> </mrow> </math></EquationSource> </InlineEquation> vertices is <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-reconstructible.</p>

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

Trees with at Least \(6\ell +11\) Vertices are \(\ell \)-Reconstructible

  • 期刊论文

  • 发表日期：

    2025年12月1日

查看全文
  • Alexandr V. Kostochka,
  • Mina Nahvi,
  • Douglas B. West,
  • Dara Zirlin

摘要

The \((n-\ell )\) ( n - ℓ ) -deck of an n-vertex graph is the multiset of (unlabeled) subgraphs obtained from it by deleting \(\ell \) ℓ vertices. An n-vertex graph is \(\ell \) ℓ -reconstructible if it is determined by its \((n-\ell )\) ( n - ℓ ) -deck, meaning that no other graph has the same deck. We prove that every tree with at least \(6\ell +11\) 6 ℓ + 11 vertices is \(\ell \) ℓ -reconstructible.