End-Devouring Rays

Low ★ Graph Theory » Infinite Graphs accessible to undergrads

Author: Georgakopoulos, Agelos— posted by Agelos on 2008-02-03

Status solved high confidence

Gollin and Heuer (2017/2018) proved that every end $\omega$ of a graph either contains uncountably many disjoint rays or admits a set of disjoint $\omega$-rays that devours $\omega$ and starts at any prescribed feasible set of starting vertices. Their theorem explicitly confirms Georgakopoulos's conjecture, settling the case of countable ends with an arbitrary (in particular, infinite) set $K$ of pairwise disjoint $\omega$-rays.

Cited literature (1)

proof Infinite end-devouring sets of rays with prescribed start vertices (2018)

J. Pascal Gollin, Karl Heuer · Discrete Mathematics · arXiv:1704.06577 · doi:10.1016/j.disc.2018.04.012

Proves that every end of a graph either contains uncountably many disjoint rays or contains a set of disjoint rays devouring the end with any prescribed feasible set of start vertices, confirming Georgakopoulos's conjecture and resolving the End-Devouring Rays problem for countable ends.

Reviewer notes. The arXiv abstract page (1704.06577) explicitly states the result confirms Georgakopoulos's conjecture. The journal version appeared in Discrete Mathematics 341 (2018), pp. 2117-2120, DOI 10.1016/j.disc.2018.04.012.

Auto-reviewed 2026-05-08 with claude-sonnet (subagent) (web search enabled).

Problem. Let $ G $ be a graph, $ \omega $ a countable end of $ G $ , and $ K $ an infinite set of pairwise disjoint $ \omega $ -rays in $ G $ . Prove that there is a set $ K' $ of pairwise disjoint $ \omega $ -rays that devours $ \omega $ such that the set of starting vertices of rays in $ K' $ equals the set of starting vertices of rays in $ K $ .

Keywords: end · ray

Discussion

We say that a set of rays $ K $ devours the end $ \omega $ if every ray in $ \omega $ meets some ray in $ K $ . An end is countable if there is a countable set of rays devouring it. If $ K $ is a finite set of rays then it is not hard to prove (see [G]) that this problem has a positive answer: Theorem For every graph $ G $ and every countable end $ \omega $ of $ G $ , if $ G $ has a set $ K $ of $ k\in \mathcal N $ pairwise disjoint $ \omega $ -rays, then it also has a set $ K' $ of $ k $ pairwise disjoint $ \omega $ -rays that devours $ \omega $ . Moreover, $ K' $ can be chosen so that its rays have the same starting vertices as the rays in~ $ K $ .

Bibliography

★ [G] A. Georgakopoulos, Infinite Hamilton Cycles in Squares of Locally Finite Graphs, Preprint.