4-连通图的一种Tutte型典范分解

A Tutte-type canonical decomposition of 4-connected graphs

摘要 Abstract

我们为每个4-连通图提供了一种独特的分解,其组成部分要么是拟5-连通的,要么是三角躯体和至多5个顶点的3-连通躯体构成的三角循环,或者是广义双轮,或者是增厚的$K_{4,m}$。该分解可以用允许存在于粘连集中的边的树分解来描述。我们的构造是显式的、典范的,并且展示了Tutte分解的一个定义特性。作为推论,我们得到了3-连通图的一种新的Tutte型典范分解,其组成部分要么是拟4-连通的,要么是广义轮,要么是增厚的$K_{3,m}$。这种分解与三分离分解相似但不同。作为4-连通性的分解应用,我们得到了一个新的定理,该定理刻画了所有4-连通有限点传递图,即为拟5-连通图、拟5-连通图的$K_4$扩张,或者是一份简短的显式列表上的图。

We provide a unique decomposition of every 4-connected graph into parts that are either quasi-5-connected, cycles of triangle-torsos and 3-connected torsos on $\leq 5$ vertices, generalised double-wheels, or thickened $K_{4,m}$'s. The decomposition can be described in terms of a tree-decomposition but with edges allowed in the adhesion-sets. Our construction is explicit, canonical, and exhibits a defining property of the Tutte-decomposition. As a corollary, we obtain a new Tutte-type canonical decomposition of 3-connected graphs into parts that are either quasi-4-connected, generalised wheels or thickened $K_{3,m}$'s. This decomposition is similar yet different from the tri-separation decomposition. As an application of the decomposition for 4-connectivity, we obtain a new theorem characterising all 4-connected vertex-transitive finite graphs as quasi-5-connected, the $K_4$-expansion of a quasi-5-connected graph, or on a short explicit list of graphs.