论文标题
2.5连接性：独特的组件，关键图和应用
2.5-Connectivity: Unique Components, Critical Graphs, and Applications
论文作者
论文摘要
如果双连接图在去除任意顶点和任意边缘后保持连接，则称为2.5连接。我们证明，每个双连接图都具有2.5个连接组件的规范分解。这些组件在树结构中排列。我们还讨论了2.5个连接的组件与三连电组件之间的连接，并使用它来呈现线性时间算法，该算法计算图形的2.5连接组件。我们表明，使用简单的图形操作，可以从关键的2.5连接较小阶的关键图中获得除K4以外的所有关键图形。此外，我们在周期分解和周期包装的背景下演示了2.5个连接组件的应用。
If a biconnected graph stays connected after the removal of an arbitrary vertex and an arbitrary edge, then it is called 2.5-connected. We prove that every biconnected graph has a canonical decomposition into 2.5-connected components. These components are arranged in a tree-structure. We also discuss the connection between 2.5-connected components and triconnected components and use this to present a linear-time algorithm which computes the 2.5-connected components of a graph. We show that every critical 2.5-connected graph other than K4 can be obtained from critical 2.5-connected graphs of smaller order using simple graph operations. Furthermore, we demonstrate applications of 2.5-connected components in the context of cycle decompositions and cycle packings.
