On independent spanning trees

Samir Khuller; Baruch Schieber

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

On independent spanning trees

Samir Khuller, Baruch Schieber

Research output: Contribution to journal › Article › peer-review

39 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
Externally published	Yes

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

Access to Document

10.1016/0020-0190(92)90230-S

Cite this

@article{f2d3dac09cf64d858112eb83c8dd4cf6,

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

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this