On spanning trees and \(k\)-connectedness in infinite graphs
type: Item
instance of: scholarly article
title: On spanning trees and \(k\)-connectedness in infinite graphs
zbMATH Open document ID: 0780.05013
DOI: 10.1016/0095-8956(92)90022-P
published in: Journal of Combinatorial Theory. Series B
publication date: 1993-03-10T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 130557
zbMATH Keywords: \(k\)-connectedness
zbMATH Keywords: spanning tree
zbMATH Keywords: infinite graph
zbMATH Keywords: end
zbMATH Keywords: connected graph
zbMATH Keywords: end-faithful
zbMATH Keywords: tree-decomposition
zbMATH Keywords: factors
author: Reinhard Diestel
reviewed by: Martin Škoviera
MaRDI profile type: Publication
cites work: Q3999150
cites work: On end-faithful spanning trees in infinite graphs
cites work: The end structure of a graph: Recent results and open problems
cites work: Über unendliche Wege in Graphen
cites work: Q3929755
cites work: Bounded graphs
cites work: Q3484856
cites work: Ein Ordnungsbegriff für Graphen ohne unendliche Wege mit einer Anwendung auf n-fach zusammenhaengende Graphen
cites work: An end-faithful spanning tree counterexample
cites work: Infinite connected graphs with no end-preserving spanning trees
description: scientific article; zbMATH DE number 130557