Steiner tree packing number and tree connectivity |
| |
Authors: | Hengzhe Li Baoyindureng Wu Jixiang Meng Yingbin Ma |
| |
Institution: | 1. College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, PR China;2. College of Mathematics and System Sciences, Xinjiang University, Urumqi 830046, PR China |
| |
Abstract: | Let be a set of at least two vertices in a graph . A subtree of is a -Steiner tree if . Two -Steiner trees and are edge-disjoint (resp. internally vertex-disjoint) if (resp. and ). Let (resp. ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) -Steiner trees in , and let (resp. ) be the minimum (resp. ) for ranges over all -subset of . Kriesell conjectured that if for any , then . He proved that the conjecture holds for . In this paper, we give a short proof of Kriesell’s Conjecture for , and also show that (resp. ) if (resp. ) in , where . Moreover, we also study the relation between and , where is the line graph of . |
| |
Keywords: | Connectivity Edge-connectivity Packing Steiner trees Tree connectivity Line graph |
本文献已被 ScienceDirect 等数据库收录! |
|