论文标题
转移到可避免的路径
Shifting paths to avoidable ones
论文作者
论文摘要
图$ g $中诱导的路径$ p $的扩展是一种诱导的路径$ p'$，因此删除$ p'$结果$ p $中的端点。如果图形中的每个延伸物中都包含在诱导的循环中，则可以避免图形中的诱导路径。 2019年，Beisegel，Chudovsky，Gurvich，Milanič和Servatius猜想，每个包含诱导的$ K $ vertex路径的图形也包含相同长度的可避免的诱导路径，并证明了$ K = 2 $的结果。由于Ohtsuki，Cheung和Fujisawa的工作，$ K = 1 $的案例早于1976年。在本文中，使用类似的方法，我们从重新配置的角度加强了它们的结果。也就是说，我们表明，在每个图中，每个诱导的路径都可以通过一系列偏移转换为可避免的路径，如果它们的结合是$ k+1 $ pertices的诱导路径，则两个诱导的$ k $ vertex路径彼此相移。我们还获得了不一定引起的路径和步行的类似结果。相反，该语句不能扩展到跟踪或等距路径。
An extension of an induced path $P$ in a graph $G$ is an induced path $P'$ such that deleting the endpoints of $P'$ results in $P$. An induced path in a graph is said to be avoidable if each of its extensions is contained in an induced cycle. In 2019, Beisegel, Chudovsky, Gurvich, Milanič, and Servatius conjectured that every graph that contains an induced $k$-vertex path also contains an avoidable induced path of the same length, and proved the result for $k = 2$. The case $k = 1$ was known much earlier, due to a work of Ohtsuki, Cheung, and Fujisawa in 1976. The conjecture was proved for all $k$ in 2020 by Bonamy, Defrain, Hatzel, and Thiebaut. In the present paper, using a similar approach, we strengthen their result from a reconfiguration point of view. Namely, we show that in every graph, each induced path can be transformed to an avoidable one by a sequence of shifts, where two induced $k$-vertex paths are shifts of each other if their union is an induced path with $k+1$ vertices. We also obtain analogous results for not necessarily induced paths and for walks. In contrast, the statement cannot be extended to trails or to isometric paths.
