Scholarlink

<p>It is known that, if removing some <i>n</i> edges from a graph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1400_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Gamma \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation> destroys all subgraphs isomorphic to a given finite graph <i>K</i>, then all subgraphs isomorphic to <i>K</i> can be destroyed by removing at most <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1400_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="78" /> </InlineMediaObject> <EquationSource Format="TEX">\(|E(K)|\cdot n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>E</mi> <mo stretchy="false">(</mo> <mi>K</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo>·</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> edges, which form a set invariant with respect to all automorphisms of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1400_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Gamma \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation>. We construct the first examples of (connected) graphs <i>K</i> for which this estimate is not sharp. Our arguments are based on a “weighted analogue” of an earlier known estimate for the cost of symmetry.</p>

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

Invariant systems of weighted representatives

  • 期刊论文

  • 发表日期：

    2025年3月26日

查看全文
  • Anton A. Klyachko,
  • Mikhail S. Terekhov

摘要

It is known that, if removing some n edges from a graph \(\Gamma \) Γ destroys all subgraphs isomorphic to a given finite graph K, then all subgraphs isomorphic to K can be destroyed by removing at most \(|E(K)|\cdot n\) | E ( K ) | · n edges, which form a set invariant with respect to all automorphisms of \(\Gamma \) Γ . We construct the first examples of (connected) graphs K for which this estimate is not sharp. Our arguments are based on a “weighted analogue” of an earlier known estimate for the cost of symmetry.