Edge-disjoint trees containing some given vertices in a graph
type: Item
instance of: scholarly article
title: Edge-disjoint trees containing some given vertices in a graph
zbMATH Open document ID: 1027.05023
DOI: 10.1016/S0095-8956(02)00013-8
author: Matthias Kriesell
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-25T00:00:00Z
review text: The graphs \(G\) considered are finite and may contain multiple edges. The edge-connectivity \(\lambda (x,y;G)\) of distinct vertices \(x,y\) of \(G\) is the largest number \(\lambda \) such that there is a system of \(\lambda \) edge-disjoint \(x,y\) paths in \(G\). A set \(A\) of vertices of \(G\) is \(n\)-edge-connected if \(\lambda (x,y;G)\geq n\) for all \(x\neq y\) in \(A.\) A subtree \(T\) of \(G\) is called an \(A\)-spanning tree if \(A\) is contained in the vertices of \(T\). An aim of this work is to show there exists a natural number \(f_h(k)\) (\(g_h(k))\) such that for every \(f_h(k)\)-edge-connected (\(g_h(k)\)-edge connected) vertex set \(A\) of \(G\) with \(|A|\leq h\) (\(|V(G)-A|\leq h\)), there exists a system of \(k\) edge-disjoint \(A\)-spanning trees. Conjecture 1 says \(f_h(k)\leq 2k.\) It is shown that \(f_3(k)=\left\lfloor \frac{8k+3}6\right\rfloor .\) And the smallest numbers \(f_h^{*}(k)\) are determined such that every \(f_h^{*}(k)\)-edge connected graph on at most \(h\) vertices contains a system of \(k\) edge-disjoint spanning trees. Applications to line graphs are given.
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1970676
zbMATH Keywords: edge-connected
zbMATH Keywords: spanning tree
reviewed by: Audrey A. Terras
MaRDI profile type: Publication
cites work: Q5422499
cites work: Q4342632
cites work: Short proofs of theorems of Nash-Williams and Tutte
cites work: Q4113856
cites work: Eine Reduktionsmethode für den Kantenzusammenhang in Graphen
cites work: Edge-Disjoint Spanning Trees of Finite Graphs
cites work: Paths and edge-connectivity in graphs
cites work: On the Problem of Decomposing a Graph into n Connected Factors
cites work: Q4378635
description: scientific article; zbMATH DE number 1970676