Countably determined ends and graphs

DOI10.1016/J.JCTB.2022.04.002MaRDI QIDQ2673479zbMATH OpenOpenAlexFDO

Authors Jan Kurkofka, Ruben Melcher

Publication date 10 June 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.07247

zbMATH Keywords

axioms of countabilitycountably determinedfirst countable end spaceinfinite graphnormal treesecond countable end spacetree-decomposition

Mathematics Subject Classification ID

Infinite graphs (05C63) Base properties of topological spaces (54D70) Topological characterizations of particular spaces (54F65)

Abstract: The directions of an infinite graph $G$ are a tangle-like description of its ends: they are choice functions that choose compatibly for all finite vertex sets $XsubseteqV(G)$ a component of $G-X$. Although every direction is induced by a ray, there exist directions of graphs that are not uniquely determined by any countable subset of their choices. We characterise these directions and their countably determined counterparts in terms of star-like substructures or rays of the graph. Curiously, there exist graphs whose directions are all countably determined but which cannot be distinguished all at once by countably many choices. We structurally characterise the graphs whose directions can be distinguished all at once by countably many choices, and we structurally characterise the graphs which admit no such countably many choices. Our characterisations are phrased in terms of normal trees and tree-decompositions. Our four (sub)structural characterisations imply combinatorial characterisations of the four classes of infinite graphs that are defined by the first and second axiom of countability applied to their end spaces: the two classes of graphs whose end spaces are first countable or second countable, respectively, and the complements of these two classes.

Recommendations

• Ends and multi-endings. I
• End spaces and tree-decompositions
• Ends and multi-endings. II
• Edge-ends in countable graphs
• Ends of graphs

Cites work

• Approximating infinite graphs by normal trees
• Canonical trees of tree-decompositions
• Duality theorems for stars and combs I: Arbitrary stars and combs
• End spaces and spanning trees
• End spaces of graphs are normal
• Ends and multi-endings. I
• Ends and multi-endings. II
• Ends and tangles
• Ends, tangles and critical vertex sets
• Graph-theoretical versus topological ends of graphs.
• scientific article; zbMATH DE number 42114 (Why is no real title available?)
• Tangles and the Stone-Čech compactification of infinite graphs
• Über unendliche Wege in Graphen
• Wurzelbäume und unendliche Wege in Graphen

Cited in

(4)

• On a problem of Cameron's on inexhaustible graphs
• scientific article; zbMATH DE number 1139012 (Why is no real title available?)
• End spaces and tree-decompositions
• A representation theorem for end spaces of infinite graphs

This page was built for publication: Countably determined ends and graphs

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