On the maximal distance of spanning trees
Research output: Contribution to journal › Article › Research › peer-review
Authors
External Organisational units
- Institute of Materials Science and Technology
Abstract
Using Ore's definition of the distance of spanning trees in a connected graph G, we determine the maximal distance a spanning tree may have from a given spanning tree and develop an algorithm for the construction of two spanning trees with maximal distance. It is also shown that the maximal distance of spanning tress in G is equal to the cyclomatic number c(G) of G, if G has no bridges and if c(G)≤min(5, |G|−1).
Details
Original language | English |
---|---|
Pages (from-to) | 378-385 |
Number of pages | 8 |
Journal | Journal of Combinatorial Theory |
Volume | 5.1968 |
Issue number | 4 |
DOIs | |
Publication status | Published - Dec 1968 |
Externally published | Yes |