k-Connectivity and Decomposition of Graphs into Forests
k-Connectivity and Decomposition of Graphs into Forests
复制标题
k-连通性和图分解成森林
DOI：
10.1016/0166-218x(94)90015-9
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
S. Poljak
中科院分区：
文献类型：
--
作者：
Takao Nishizeki;S. Poljak
我们证明，对于每一个（边）连通图g，存在一个序列et1，T2，…， tk生成树，其性质为：1 T2 \h。对于每一个j= 1，…，k，都要连通。Nagamochi和Ibaraki最近提出了一种线性时间分解程序，通过该程序可以构造这样的树序列。讨论了这一过程的一些性质及其与图的任意性的关系。
We show that, for everyk-(edge) connected graphG, there exists a sequenceT1,T2,...,Tkof spanning trees with the property thatT1⌣T2⌣ \h. ⌣Tjisj-(edge) connected for everyj= 1,...,k. Nagamochi and Ibaraki have recently presented a linear time decomposition procedure by which such a sequence of trees can be constructed. We discuss some properties of this procedure and its relation to the arboricity of a graph.