Premium
End‐faithful spanning trees in T 1 ‐free graphs
Author(s) -
Polat Norbert
Publication year - 1997
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/(sici)1097-0118(199712)26:4<175::aid-jgt1>3.0.co;2-n
Subject(s) - combinatorics , mathematics , spanning tree , counterexample , trémaux tree , subdivision , discrete mathematics , tree (set theory) , graph , minimum degree spanning tree , line graph , pathwidth , archaeology , history
We prove that any connected graph that contains no subdivision of an ℵ 1 ‐regular tree has an end‐faithful spanning tree; and furthermore that it has a rayless spanning tree if all its ends are dominated. This improves a result of Seymour and Thomas (An end‐faithful spanning tree counterexample, Discrete Math. 95 (1991)). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 175–181, 1997