Title: Edge-disjoint trees containing some given vertices in a graph
Abstract: We show that for any two natural numbers k,ℓ there exist (smallest natural numbers fℓ(k)(gℓ(k)) such that for any fℓ(k)-edge-connected (gℓ(k)-edge-connected) vertex set A of a graph G with |A|⩽ℓ(|V(G)−A|⩽ℓ) there exists a system T of k edge-disjoint trees such that A⊆V(T) for each T∈T. We determine f3(k)=⌊8k+36⌋. Furthermore, we determine for all natural numbers ℓ,k the smallest number fℓ∗(k) such that every fℓ∗(k)-edge-connected graph on at most ℓ vertices contains a system of k edge-disjoint spanning trees, and give applications to line graphs.
Publication Year: 2003
Publication Date: 2003-05-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 79
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot