Reconfiguration of Regular Induced Subgraphs
Reconfiguration of Regular Induced Subgraphs
复制标题
正则诱导子图的重新配置
DOI：
10.1007/978-3-030-96731-4_4
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Wasa Kunihiro
中科院分区：
文献类型：
--
作者：
Eto Hiroshi;Ito Takehiro;Kobayashi Yasuaki;Otachi Yota;Wasa Kunihiro
研究了图中d正则诱导子图的分步变换是否存在的问题，该变换的每一步都必须遵循一个固定的重构规则。我们的问题等价于独立集重构，这是研究得最好的重构问题之一。在本文中，我们系统地研究了问题的复杂性，特别是弦图和二部图。我们的结果与已知的独立集重构结果形成了有趣的对比。
We study the problem of checking the existence of a step-by-step transformation ofd-regular induced subgraphs in a graph, whereand each step in the transformation must follow a fixed reconfiguration rule. Our problem foris equivalent toIndependent Set Reconfiguration, which is one of the most well-studied reconfiguration problems. In this paper, we systematically investigate the complexity of the problem, in particular, on chordal graphs and bipartite graphs. Our results give interesting contrasts to known ones forIndependent Set Reconfiguration.