×

\(k\)-connectivity and decomposition of graphs into forests. (English) Zbl 0818.05043

The authors show that for every \(k\)-(edge) connected graph there exists a sequence of spanning trees \((T_ 1,\dots, T_ k)\), such that \(T_ 1\cup T_ 2\cup\cdots \cup T_ j\) is \(j\)-(edge) connected for every \(1\leq j\leq k\).
Reviewer: M.Hager (Leonberg)

MSC:

05C40 Connectivity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobas, B., Extremal Graph Theory (1978), Academic Press: Academic Press New York · Zbl 0419.05031
[2] Cheriyan, J.; Thurimella, R., Algorithms for parallel \(k\)-vertex connectivity and sparse certificates, Proceedings 23rd Annual Symposium on Theory of Computing, 391-401 (1991)
[3] Dean, A. M.; Hutchinson, J. P.; Scheinerman, E. R., On the thickness and arboricity of a graph, J. Combin. Theory Ser. B, 52, 147-151 (1991) · Zbl 0675.05042
[4] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[5] Gabow, H. N.; Westerman, H. H., Forests, frames and games: Algorithms for matroid sums and applications, Proceedings of 20th Annual ACM Symposium on Theory of Computing, Chicago, IL (1988)
[6] Kundu, S., Bounds on the number of disjoint spanning trees, J. Combin. Theory Ser. B, 17, 199-203 (1974) · Zbl 0285.05113
[7] Mader, W., Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen, Arch. Math., 23, 219-224 (1972) · Zbl 0212.29402
[8] Nagamochi, N.; Ibaraki, T., A linear-time algorithm for finding a sparse \(k\)-connected subgraph of a \(k\)-connected graphs, Algorithmica, 7, 583-596 (1992) · Zbl 0763.05065
[9] Nagamochi, N.; Ibaraki, T., Computing edge-connectivity in multiple and capacitated graphs, (Asano, T.; Ibaraki, T.; Imai, H.; Nishizeki, T., Algorithms, Proceedings International Symposium SIGAL ’90, Lecture Notes in Computer Science, 450 (1991), Springer: Springer Berlin), 12-20
[10] Suzuki, H.; Takahashi, N.; Nishizeki, T.; Miyamo, H.; Ueno, S., An algorithm for tripartitioning 3-connected graphs, Inform. Process. Soc., 31, 584-592 (1990)
[11] Tarjan, R. J., Data Structures and Network Algorithms (1983), SIAM: SIAM Philadelphia, PA · Zbl 0584.68077
[12] Welsh, D. J., Matroid Theory (1976), Academic Press: Academic Press New York · Zbl 0343.05002
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.