On independent spanning trees

Samir Khuller, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

39 Scopus citations


We prove that if any k-vertex connected graph has k vertex independent spanning trees, then any k-edge connected graph has k edge independent spanning trees. Thus, answering a question raised by Zehavi and Itai [J. Graph Theory 13 (1989)] in the affirmative.

Original languageEnglish (US)
Pages (from-to)321-323
Number of pages3
JournalInformation Processing Letters
Issue number6
StatePublished - Jul 24 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


  • Combinatorial problems
  • edge connectivity
  • spanning trees
  • vertex connectivity


Dive into the research topics of 'On independent spanning trees'. Together they form a unique fingerprint.

Cite this