Skip to main content
Log in

Independent trees in graphs

  • Original Papers
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

IfG is a finite undirected graph ands is a vertex ofG, then two spanning treesT 1 andT 2 inG are calleds — independent if for each vertexx inG the paths fromx tos inT 1 andT 2 are openly disjoint. It is known that the following statement is true fork≤3: IfG isk-connected, then there arek pairwises — independent spanning, trees inG. As a main result we show that this statement is also true fork=4 if we restrict ourselves to planar graphs. Moreover we consider similar statements for weaklys — independent spanning trees (i.e., the tree paths from a vertex tos are edge disjoint) and for directed graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Cheriyan, J., Maheshwari, S.N.: Finding nonseparating induced cycles and independent spanning trees in 3 — connected graphs. J. Algorithms9, 507–537 (1988)

    Google Scholar 

  2. Edmonds, J.: Submodular functions, matroids and certain polyhedra. In: Combinatorial Structures and Their Applications, R. Guy et al, Eds. Gordon and Breach, New York, 1969, pp. 69–87

    Google Scholar 

  3. Hopcroft, J., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comp.2, 135–158 (1973)

    Google Scholar 

  4. Itai, A., Rodeh, R.: The multi-tree approach to reliability in distributed networks. Proceedings 25th Annual IEEE Symposium on Foundations of Computer Sciences, 1984, pp. 137–147

  5. Khuller, S., Schieber, B.: On independent spanning trees. Inform. Process. Lett.42, (6), 321–323 (1992)

    Google Scholar 

  6. Mader, W.: A reduction method for edge-connectivity in graphs. Ann. discrete Math3, 145–164 (1978)

    Google Scholar 

  7. Mader, W.: Path in graphs, reducings the edge-connectivity only by two. Graphs and Combinatorics1, 81–89 (1985)

    Google Scholar 

  8. Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comp.1, 146–160 (1972)

    Google Scholar 

  9. Whitty, R.W.: Vertex-disjoint paths and edge-disjoint branchings in directed graphs. J. Graph Theory11, 349–358 (1987)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Huck, A. Independent trees in graphs. Graphs and Combinatorics 10, 29–45 (1994). https://doi.org/10.1007/BF01202468

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01202468

Keywords

Navigation