Scholarlink

<p>An arborescence in a digraph is an acyclic arc subset in which every vertex except a root has exactly one incoming arc. In this paper, we show the reconfigurability of the union of <i>k</i> arborescences for fixed <i>k</i> in the following sense: for any pair of arc subsets that can be partitioned into <i>k</i> arborescences, one can be transformed into the other by exchanging arcs one by one so that every intermediate arc subset can also be partitioned into <i>k</i> arborescences. This generalizes the result by Ito et al.&#xa0;(2023), who showed the case with <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1310_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(k=1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. Since the union of <i>k</i> arborescences can be represented as a common matroid basis of two matroids, our result gives a new non-trivial example of matroid pairs for which two common bases are always reconfigurable to each other.</p>

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

Reconfiguration of the Union of Arborescences

  • 期刊论文

  • 发表日期：

    2025年4月11日

查看全文
  • Yusuke Kobayashi,
  • Ryoga Mahara,
  • Tamás Schwarcz

摘要

An arborescence in a digraph is an acyclic arc subset in which every vertex except a root has exactly one incoming arc. In this paper, we show the reconfigurability of the union of k arborescences for fixed k in the following sense: for any pair of arc subsets that can be partitioned into k arborescences, one can be transformed into the other by exchanging arcs one by one so that every intermediate arc subset can also be partitioned into k arborescences. This generalizes the result by Ito et al. (2023), who showed the case with \(k=1\) k = 1 . Since the union of k arborescences can be represented as a common matroid basis of two matroids, our result gives a new non-trivial example of matroid pairs for which two common bases are always reconfigurable to each other.