On spanning trees and \(k\)-connectedness in infinite graphs (Q1204461): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 06:12, 31 January 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
    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

    Identifiers