On tree-decompositions of one-ended graphs

Johannes Carmesin, Florian Lehner*, Rögnvaldur G. Möller

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

A graph is one-ended if it contains a ray (a one way infinite path) and whenever we remove a finite number of vertices from the graph then what remains has only one component which contains rays. A vertex v dominates a ray in the end if there are infinitely many paths connecting v to the ray such that any two of these paths have only the vertex v in common. We prove that if a one-ended graph contains no ray which is dominated by a vertex and no infinite family of pairwise disjoint rays, then it has a tree-decomposition such that the decomposition tree is one-ended and the tree-decomposition is invariant under the group of automorphisms. This can be applied to prove a conjecture of Halin from 2000 that the automorphism group of such a graph cannot be countably infinite and solves a recent problem of Boutin and Imrich. Furthermore, it implies that every transitive one-ended graph contains an infinite family of pairwise disjoint rays.

Original languageEnglish
Pages (from-to)524-539
Number of pages16
JournalMathematische Nachrichten
Volume292
Issue number3
DOIs
Publication statusPublished - Mar 2019

Keywords

  • 05C05
  • 05C40
  • 05C63
  • 20B27
  • graph automorphism
  • infinite graph
  • tree decomposition

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'On tree-decompositions of one-ended graphs'. Together they form a unique fingerprint.

Cite this