Premium
End‐faithful spanning trees in graphs without normal spanning trees
Author(s) -
Bürger Carl,
Kurkofka Jan
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22813
Subject(s) - combinatorics , mathematics , spanning tree , pathwidth , discrete mathematics , chordal graph , treewidth , indifference graph , trémaux tree , cograph , 1 planar graph , graph , line graph
Schmidt characterised the class of rayless graphs by an ordinal rank function, which makes it possible to prove statements about rayless graphs by transfinite induction. Halin asked whether Schmidt's rank function can be generalised to characterise other important classes of graphs. In this paper, we address Halin's question: we characterise an important class of graphs by an ordinal function. Another largely open problem raised by Halin asks for a characterisation of the class of graphs with an end‐faithful spanning tree. A well‐studied subclass is formed by the graphs with a normal spanning tree. We determine a larger subclass, the class of normally traceable graphs, which consists of the connected graphs with a rayless tree‐decomposition into normally spanned parts. Investigating the class of normally traceable graphs further we prove that, for every normally traceable graph, having a rayless spanning tree is equivalent to all its ends being dominated. Our proofs rely on a characterisation of the class of normally traceable graphs by an ordinal rank function that we provide.