On the maximal distance of spanning trees
Publikationen: Beitrag in Fachzeitschrift › Artikel › Forschung › (peer-reviewed)
Autoren
Externe Organisationseinheiten
- Technische Universität Wien
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
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 378-385 |
| Seitenumfang | 8 |
| Fachzeitschrift | Journal of Combinatorial Theory |
| Jahrgang | 5.1968 |
| Ausgabenummer | 4 |
| DOIs | |
| Status | Veröffentlicht - Dez. 1968 |
| Extern publiziert | Ja |
