首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 S be a set of at least two vertices in a graph G. A subtree T of G is a S-Steiner tree if S?V(T). Two S-Steiner trees T1 and T2 are edge-disjoint (resp. internally vertex-disjoint) if E(T1)E(T2)=? (resp. E(T1)E(T2)=? and V(T1)V(T2)=S). Let λG(S) (resp. κG(S)) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) S-Steiner trees in G, and let λk(G) (resp. κk(G)) be the minimum λG(S) (resp. κG(S)) for S ranges over all k-subset of V(G). Kriesell conjectured that if λG({x,y})2k for any x,yS, then λG(S)k. He proved that the conjecture holds for |S|=3,4. In this paper, we give a short proof of Kriesell’s Conjecture for |S|=3,4, and also show that λk(G)1k?1k?2 (resp. κk(G)1k?1k?2 ) if λ(G)? (resp. κ(G)?) in G, where k=3,4. Moreover, we also study the relation between κk(L(G)) and λk(G), where L(G) is the line graph of G.
Keywords:Connectivity  Edge-connectivity  Packing Steiner trees  Tree connectivity  Line graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号