On spanning trees and \(k\)-connectedness in infinite graphs (Q1204461): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Reinhard Diestel / rank | |||
Property / reviewed by | |||
Property / reviewed by: Martin Škoviera / rank | |||
Revision as of 03:01, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On spanning trees and \(k\)-connectedness in infinite graphs |
scientific article |
Statements
On spanning trees and \(k\)-connectedness in infinite graphs (English)
0 references
10 March 1993
0 references
Every spanning tree \(T\) of an infinite graph \(G\) gives rise to a natural mapping which sends an arbitrary end of \(T\) to the end of \(G\) containing it. A spanning tree for which this mapping is a bijection is called end- faithful. Halin (1964), who was the first to study these concepts, showed that a countably infinite connected graph always contains an end-faithful spanning tree. Very recently, \textit{P. Seymour} and \textit{R. Thomas} [Discrete Math. 95, No. 1-3, 321-330 (1991; Zbl 0763.05032)] and independently \textit{C. Thomassen} [J. Comb. Theory, Ser. B 54, No. 2, 322- 324 (1992; Zbl 0753.05030)] gave examples of graphs that have no end- faithful spanning tree. The author, answering a question posed by J. Širáň, proves the following. Theorem A. The spanning trees of a connected graph \(G\) are all end- faithful if and only if every block of \(G\) is rayless, i.e., has no one- way infinite path. This result immediately raises a further question: What do the 2- connected rayless graphs look like? The author gives the following answer, in fact a more general result of independent interest. Theorem B. An infinite graph is rayless and \(k\)-connected if and only if it has a \(k\)-connected rayless tree-decomposition into finite \(k\)- connected factors.
0 references
\(k\)-connectedness
0 references
spanning tree
0 references
infinite graph
0 references
end
0 references
connected graph
0 references
end-faithful
0 references
tree-decomposition
0 references
factors
0 references