On tree‐decompositions of one‐ended graphs |
| |
Authors: | Johannes Carmesin,Florian Lehner,R gnvaldur G. M ller |
| |
Affiliation: | Johannes Carmesin,Florian Lehner,Rögnvaldur G. Möller |
| |
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. |
| |
Keywords: | graph automorphism infinite graph tree decomposition 20B27 05C05 05C40 05C63 |
|
|