Bounds on the number of disjoint spanning trees
Bounds on the number of disjoint spanning trees
复制标题
DOI：
10.1016/0095-8956(74)90087-2
复制
发表时间：
1974-10
期刊：
影响因子：
--
通讯作者：
S. Kundu
中科院分区：
文献类型：
--
作者：
S. Kundu
证明了一个n边连通图至少有<$（n-1）2个n边不相交的成对生成树。一般来说，这个界限是最好的。一个顶点数为4或4以上的极大平面图包含两棵边不相交的生成树。对于一个极大的环形图，这个数是3。
It is shown that an n-edge connected graph has at least⌈(n− 1) 2⌉ pairwise edge-disjoint spanning trees. This bound is best possible in general. A maximal planar graph with four or more vertices contains two edge-disjoint spanning trees. For a maximal toroidal graph, this number is three.