Ubiquity in graphs II: Ubiquity of graphs with nowhere-linear end structure

Abstract

A graph $G$ is said to be $⪯$-ubiquitous, where $⪯$ is the minor relation between graphs, if whenever $\Gamma$ is a graph with $nG⪯\Gamma$ for all $n\in \mathbb{N}$, then one also has ${\aleph }_{0}G⪯\Gamma$, where $\alpha G$ is the disjoint union of $\alpha$ many copies of $G$. A well-known conjecture of Andreae is that every locally finite connected graph is $⪯$-ubiquitous. In this paper we give a sufficient condition on the structure of the ends of a graph~$G$ which implies that $G$ is $⪯$-ubiquitous. In particular this implies that the full grid is $⪯$-ubiquitous.

38 pages, 3 figures