On independent spanning trees

Samir Khuller; Baruch Schieber

doi:10.1016/0020-0190(92)90230-S

On independent spanning trees

Samir Khuller^*, Baruch Schieber

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	321-323
Number of pages	3
Journal	Information Processing Letters
Volume	42
Issue number	6
DOIs	https://doi.org/10.1016/0020-0190(92)90230-S
State	Published - Jul 24 1992

Keywords

Combinatorial problems
edge connectivity
spanning trees
vertex connectivity

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(92)90230-S

Cite this

@article{36cf41819ced4468add19d28ad0fe6f2,

title = "On independent spanning trees",

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.",

keywords = "Combinatorial problems, edge connectivity, spanning trees, vertex connectivity",

author = "Samir Khuller and Baruch Schieber",

note = "Funding Information: Correspo&ence to: Professor S. Khuller, Institute for Advanced Computer Studies, A.V. Williams Building, University of Maryland, College Park, MD 20742, USA. * Partially supported by NSF grants CCR-8906949, CCR-9103135 and CCR-9111348. Part of this work was done while this author was visiting the IBM T.J. Watson Research Center.",

year = "1992",

month = jul,

day = "24",

doi = "10.1016/0020-0190(92)90230-S",

language = "English (US)",

volume = "42",

pages = "321--323",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - On independent spanning trees

AU - Khuller, Samir

AU - Schieber, Baruch

N1 - Funding Information: Correspo&ence to: Professor S. Khuller, Institute for Advanced Computer Studies, A.V. Williams Building, University of Maryland, College Park, MD 20742, USA. * Partially supported by NSF grants CCR-8906949, CCR-9103135 and CCR-9111348. Part of this work was done while this author was visiting the IBM T.J. Watson Research Center.

PY - 1992/7/24

Y1 - 1992/7/24

N2 - 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.

AB - 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.

KW - Combinatorial problems

KW - edge connectivity

KW - spanning trees

KW - vertex connectivity

UR - http://www.scopus.com/inward/record.url?scp=0026895284&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026895284&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(92)90230-S

DO - 10.1016/0020-0190(92)90230-S

M3 - Article

AN - SCOPUS:0026895284

SN - 0020-0190

VL - 42

SP - 321

EP - 323

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

On independent spanning trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this