Edge-disjoint trees containing some given vertices in a graph

DOI10.1016/S0095-8956(02)00013-8MaRDI QIDQ1405100zbMATH OpenFDO

Authors Matthias Kriesell

Publication date 25 August 2003

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0095-8956(02)00013-8

zbMATH Keywords

edge-connected spanning tree

Mathematics Subject Classification ID

Trees (05C05)

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.

Recommendations

Cites work

Cited in

(32)

This page was built for publication: Edge-disjoint trees containing some given vertices in a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1405100)