On the maximal distance of spanning trees
Research output: Contribution to journal › Article › Research › peer-review
Standard
In: Journal of Combinatorial Theory, Vol. 5.1968, No. 4, 12.1968, p. 378-385.
Research output: Contribution to journal › Article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex - Download
}
RIS (suitable for import to EndNote) - Download
TY - JOUR
T1 - On the maximal distance of spanning trees
AU - Baron, Gerd
AU - Imrich, Wilfried
PY - 1968/12
Y1 - 1968/12
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=58149412780&partnerID=8YFLogxK
U2 - 10.1016/S0021-9800(68)80014-6
DO - 10.1016/S0021-9800(68)80014-6
M3 - Article
AN - SCOPUS:58149412780
VL - 5.1968
SP - 378
EP - 385
JO - Journal of Combinatorial Theory
JF - Journal of Combinatorial Theory
SN - 0021-9800
IS - 4
ER -
