On independent spanning trees

Samir Khuller, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

Abstract

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
Volume42
Issue number6
DOIs
StatePublished - Jul 24 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

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

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

Cite this