论文标题
可递归分区图的韧性
Toughness of recursively partitionable graphs
论文作者
论文摘要
$ n $顶点上的简单图$ g =（v，e）$，如果$ g \ simeq k_1 $，或者如果连接$ g $，则可以递归分区（RP），或者满足以下递归属性：对于每个整数分区$ a_1，a_1，a_1，a_2，a_2，a_2，a_k dots，a_k $ n $ $ n $ $ n s a a $ $ v $的a_k \} $，使每个$ | a_i | = a_i $，每个诱导的子图$ g [a_i] $ is rp（$ 1 \ leq i \ leq i \ leq k $）。我们表明，如果$ s $是带有$ | s | \ geq 2 $的RP图$ G $的顶点剪切，则$ G-S $最多具有$ 3 | S | -1 $组件。此外，对于$ | s | = 3 $，此界限是锋利的。我们提出了两种构造旧RP图的方法。我们使用这些方法来表明，对于所有正整数$ s $，存在无限的RP图，并带有$ s $ vertex剪切，其删除剩下$ 2S+1 $ $ $。此外，我们证明了图形具有RP生成树的简单必要条件，并且我们表征了一类最小的2个连接的RP图。
A simple graph $G=(V,E)$ on $n$ vertices is said to be recursively partitionable (RP) if $G \simeq K_1$, or if $G$ is connected and satisfies the following recursive property: for every integer partition $a_1, a_2, \dots, a_k$ of $n$, there is a partition $\{A_1, A_2, \dots, A_k\}$ of $V$ such that each $|A_i|=a_i$, and each induced subgraph $G[A_i]$ is RP ($1\leq i \leq k$). We show that if $S$ is a vertex cut of an RP graph $G$ with $|S|\geq 2$, then $G-S$ has at most $3|S|-1$ components. Moreover, this bound is sharp for $|S|=3$. We present two methods for constructing new RP graphs from old. We use these methods to show that for all positive integers $s$, there exist infinitely many RP graphs with an $s$-vertex cut whose removal leaves $2s+1$ components. Additionally, we prove a simple necessary condition for a graph to have an RP spanning tree, and we characterise a class of minimal 2-connected RP graphs.
