zbMATH — the first resource for mathematics

Spanning trees of locally finite graphs. (English) Zbl 0679.05023
Let \(P,P_ 0,P_ 1,..\). denote one-way infinite paths in a connected locally-finite infinite graph G. Two such paths \(P_ 1\) and \(P_ 2\) are equivalent if there exists a path \(P_ 0\) such that if P is any one-way infinite subgraph of \(P_ 0\) then P has vertices in common with both \(P_ 1\) and \(P_ 2\). Classes of equivalent paths are called ends and an end E is called free if there exists a finite set R of vertices such that G-R has a connected component that contains one-way infinite paths from E but none from any other ends of G. Let E denote a free end of G. The author proves various results on the existence of a spanning tree T of G having a specified number of ends belonging to E.
Reviewer: J.W.Moon

05C05 Trees
05C38 Paths and cycles
Full Text: EuDML
[1] Halin R.: Über unendliche Wege in Graphen. Math. Annalen 157 (1964), 125-137. · Zbl 0125.11701
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.