Premium
Edge‐disjoint spanning trees: A connectedness theorem
Author(s) -
Farber M.,
Richter B.,
Shank H.
Publication year - 1985
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190090303
Subject(s) - spanning tree , combinatorics , mathematics , social connectedness , disjoint sets , enhanced data rates for gsm evolution , discrete mathematics , sequence (biology) , minimum spanning tree , tree (set theory) , computer science , biology , genetics , psychology , telecommunications , psychotherapist
It is well known that any spanning tree of a graph can be obtained from any other by a sequence of single edge exchanges in a way that preserves, at each step, the property of being a spanning tree. We consider a variation of this problem concerning pairs of edge‐disjoint spanning trees. In particular, it is shown that any pair of edge‐disjoint spanning trees can be obtained from any other by a sequence of single edge exchanges in a way that preserves, at each step, the property of being edge‐disjoint spanning trees.