Independent Trees and Branchings in Planar Multigraphs |
| |
Authors: | Andreas Huck |
| |
Institution: | (1) Institute of Mathematics, University of Hannover, Welfengarten 1, 30167 Hannover, Germany. e-mail: huck@math.uni-hannover.de, DE |
| |
Abstract: | The following statement is proved: Let G be a finite directed or undirected planar multigraph and s be a vertex of G such that for each vertex x≠s of G, there are at least k pairwise openly disjoint paths in G from x to s where k∉{3,4,5} if G is directed. Then there exist k spanning trees T
1, … ,T
k in G directed towards s if G is directed such that for each vertex x≠s of G, the k paths from x to s in T
1, … ,T
k are pairwise openly disjoint. – The case where G is directed and k∈{3,4,5} remains open.
Received: January 30, 1995 / Revised: October 7, 1996 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|