×

zbMATH — the first resource for mathematics

On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs. (English) Zbl 1075.05050
Summary: We prove that every \(6k\)-connected graph contains \(k\) edge-disjoint rigid (and hence 2-connected) spanning subgraphs. By using this result we can settle special cases of two conjectures, due to Kriesell and Thomassen, respectively: we show that every 12-connected graph \(G\) has a spanning tree \(T\) for which \(G-E(T)\) is 2-connected, and that every 18-connected graph has a 2-connected orientation.

MSC:
05C40 Connectivity
05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A.R. Berg, T. Jordán, Two-connected orientations of Eulerian graphs, EGRES Technical Report 2004-3, submitted,
[2] J. Edmonds, Matroid partition, in: Mathematics of the Decision Sciences Part 1, Lectures in Applied Mathematics, vol. 11, AMS, Providence, RI, 1968, pp. 335-345. · Zbl 0197.00802
[3] A. Frank, Connectivity and network flows, Handbook of combinatorics, vols. 1, 2, Elsevier, Amsterdam, 1995, pp. 111-177. · Zbl 0846.05055
[4] Jackson, B.; Jordán, T., Connected rigidity matroids and unique realizations of graphs, J. combin. theory ser. B, 94, 1-29, (2005) · Zbl 1076.05021
[5] M. Kriesell, personal communication, 2003.
[6] Lovász, L.; Yemini, Y., On generic rigidity in the plane, SIAM J. algebraic discrete methods, 3, 1, 91-98, (1982) · Zbl 0497.05025
[7] Nash-Williams, C.St.J.A., Edge-disjoint spanning trees of finite graphs, J. London math. soc., 36, 445-450, (1961) · Zbl 0102.38805
[8] Schrijver, A., Combinatorial optimization, (2003), Springer Berlin · Zbl 0542.90067
[9] Thomassen, C., Configurations in graphs of large minimum degree, connectivity, or chromatic number, Ann. New York acad. sci., 555, 402-412, (1989)
[10] Tutte, W.T., On the problem of decomposing a graph into \(n\) connected factors, J. London math. soc., 36, 221-230, (1961) · Zbl 0096.38001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.