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


Pac king spanning trees and spanning 2-connected k-edge-connected essentially $$(2 k-1)$$(2 k-1)-edge-connected subgraphs
Authors:Xiaofeng Gu
Affiliation:1.Department of Mathematics,University of West Georgia,Carrollton,USA
Abstract:Let (kge 2, pge 1, qge 0) be integers. We prove that every ((4kp-2p+2q))-connected graph contains p spanning subgraphs (G_i) for (1le ile p) and q spanning trees such that all (p+q) subgraphs are pairwise edge-disjoint and such that each (G_i) is k-edge-connected, essentially ((2k-1))-edge-connected, and (G_i -v) is ((k-1))-edge-connected for all (vin V(G)). This extends the well-known result of Nash-Williams and Tutte on packing spanning trees, a theorem that every 6p-connected graph contains p pairwise edge-disjoint spanning 2-connected subgraphs, and a theorem that every ((6p+2q))-connected graph contains p spanning 2-connected subgraphs and q spanning trees, which are all pairwise edge-disjoint. As an application, we improve a result on k-arc-connected orientations.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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