Classes of locally finite ubiquitous graphs

Abstract: A classical result of Halin states that if a graph G contains n disjoint rays for every , 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 for all implies , where nA denotes the disjoint union of n copies of A (for or ). 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. [Copyright &y& Elsevier]