Classes of locally finite ubiquitous graphs

A classical result of Halin states that if a graph G contains n disjoint rays for every n∈N, then G contains infinitely many disjoint rays. The question how this generalizes to graphs other than rays leads to the notion of ubiquity: a graph A is ubiquitous with respect to a relation ⩽ between graphs (such as the subgraph relation or the minor relation) if nA⩽G for all n∈N implies ℵ0A⩽G, where nA denotes the disjoint union of n copies of A (for n∈N or n=ℵ0). A connected graph is tree-like if all its blocks are finite. The main results of the present paper establish a link between the concepts of ubiquity and well-quasi-ordering, thus offering the opportunity to apply well-quasi-ordering results (such as the graph minor theorem or Nash-Williamsʼ tree theorem) to ubiquity problems. Several corollaries are derived showing that wide classes of locally finite tree-like graphs are ubiquitous with respect to the minor or topological minor relation.