A simple existence criterion for normal spanning trees

MaRDI QIDQ286119zbMATH OpenFDO

Authors Reinhard Diestel

Publication date 20 May 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p33

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

infinite graphnormal spanning tree

Mathematics Subject Classification ID

Trees (05C05) Infinite graphs (05C63) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Review text

Summary: \textit{R. Halin} proved in 1978 [Ann. Discrete Math. 3, 93--109 (1978; Zbl 0383.05034)] that there exists a normal spanning tree in every connected graph \(G\) that satisfies the following two conditions: (i) \(G\) contains no subdivision of a `fat' \(K_{\aleph_{0}}\), one in which every edge has been replaced by uncountably many parallel edges; and (ii) \(G\) has no \(K_{\aleph_{0}}\) subgraph. We show that the second condition is unnecessary.

Recommendations

• A unified existence theorem for normal spanning trees
• Proof of Halin's normal spanning tree conjecture
• Normal Spanning Trees, Aronszajn Trees and Excluded Minors
• A new obstruction for normal spanning trees
• Minimal obstructions for normal spanning trees

Cites work

• A proof of the bounded graph conjecture
• End spaces and spanning trees
• Graph theory
• Normal Spanning Trees, Aronszajn Trees and Excluded Minors
• Simplicial Decompositions of Infinite Graphs
• Wurzelbäume und unendliche Wege in Graphen

Cited in

(9)

• Approximating infinite graphs by normal trees
• Proof of Halin's normal spanning tree conjecture
• A unified existence theorem for normal spanning trees
• Normal Spanning Trees, Aronszajn Trees and Excluded Minors
• Normal Tree Orders for Infinite Graphs
• Minimal obstructions for normal spanning trees
• A new obstruction for normal spanning trees
• A representation theorem for end spaces of infinite graphs
• Quickly proving Diestel's normal spanning tree criterion

This page was built for publication: A simple existence criterion for normal spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286119)