论文标题
提升图的分析
Analysis of the Lifting Graph
论文作者
论文摘要
通过删除两个边缘SV和SW具有共同的端s并在V和W之间添加新的边缘，可以在图形上执行“ lifting”或`拆分操作。如果这样的升力保留了与发生抬起的顶点之间的一对顶点之间的某种局部边缘连接性，则认为这样的升力是不错的。该操作对于有关边缘连接性的归纳证明很重要，可以在文献中广泛应用有关连接性增强，网络设计，方向（有限和无限图）以及边缘 - 界线链接的文献。它是由使用“分裂”一词的洛瓦斯（Lovasz）研究的，而玛德（Mader）则使用了举重一词。他们在1976年和1978年分别证明了前两个重要的结果，表明在某些条件下存在良好的升力。然后，在1980年代，其他研究人员都将其用于无向图和定向图。特别是，弗兰克（Frank）进一步调查了弗兰克（Frank），他在1992年证明了DEG（S）/2的底层良好升降机。在应用程序的激励下，约旦在1990年代后期引入了一种研究该操作的新方法。他定义并研究了“不可行性”图的结构，该图是提起图的补充。本文的主题。他证明了许多重要的结构结果，并将其应用于连通性增强。独立地，托马森（Thomassen）在2016年定义了“提升图”，并将其补充“不良图”应用于查找无限图的方向。同年晚些时候，Thomassen与OK和Richter扩展了研究，并将其结果应用于无限图中的联系。 在这里，我们对举起图的结构进行了更全面的分析。
The `lifting` or `splitting-off` operation on graphs is performed by deleting two edges sv and sw having a common end s and adding a new edge between v and w. Such a lift is considered good if it preserves a certain local edge-connectivity between the pairs of vertices different from the vertex s at which lifting takes place. The operation is important for inductive proofs concerning edge-connectivity, and can be seen widely applied in the literature on connectivity augmentation, network design, orientation (of finite and infinite graphs), and edge-disjoint linkage. It was studied by Lovasz, who used the term splitting-off, and Mader, who used the term lifting. They proved the first two significant results on it, in 1976 and 1978 respectively, showing the existence of a good lift under certain conditions. Then it was used and studied by other researchers, through the 1980s, both for undirected and directed graphs. In particular, it was investigated further by Frank who proved in 1992 that there are floor of deg(s)/2 disjoint good lifts. Motivated by the applications, a new method for studying the operation was introduced by Jordan in the late 1990s. He defined and studied the structure of the `non-admissibility` graph, which is the complement of the lifting graph; the subject of this paper. He proved a number of significant structural results on it, which he applied to connectivity augmentation. Independently, in 2016, Thomassen defined the `lifting graph`, and called its complement the `bad graph`, to apply it in finding orientations of infinite graphs. Later in the same year, Thomassen with Ok and Richter extended the study, and applied their results to linkages in infinite graphs. Here we give a more comprehensive analysis of the structure of the lifting graph.
