2020/09/07 by Carl Bürger, Bürger, Carl, Ruben Melcher +1
Computer Science · #05C05 #05C20 #05C63 #Advanced Graph Theory Research #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2009.03292
openalex publication_date 2020/09/07 · openalex created_date 2020/09/11 · openalex updated_date 2026/07/28
In a series of three papers we develop an end space theory for digraphs. Here in the third paper we introduce a concept of depth-first search trees in infinite digraphs, which we call normal spanning arborescences. We show that normal spanning arborescences are end-faithful: every end of the digraph is represented by exactly one ray in the normal spanning arborescence that starts from the root. We further show that this bijection extends to a homeomorphism between the end space of a digraph D, which may include limit edges between ends, and the end space of any normal arborescence with limit edges induced from D. Finally we prove a Jung-type criterion for the existence of normal spanning arborescences.