Classes of locally finite ubiquitous graphs

Link:
Autor/in:
Erscheinungsjahr:
2013
Medientyp:
Text
Schlagworte:
  • Infinite graphs
  • Minors
  • Topological minors
  • Tree-like graphs
  • Trees
  • Ubiquity
  • Well-quasi-ordering
Beschreibung:
  • 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. © 2012 Elsevier Inc.
Lizenz:
  • info:eu-repo/semantics/openAccess
Quellsystem:
Forschungsinformationssystem der UHH
Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/8d2b02f7-3e50-4b1f-9e42-ff7592d996f8