On tree‐decompositions of one‐ended graphs

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

Mathematische Nachrichten, 2019, vol. 292, issue 3, 524-539

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.

Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/mana.201800055

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:mathna:v:292:y:2019:i:3:p:524-539

Ordering information: This journal article can be ordered from
http://www.blackwell ... bs.asp?ref=0025-584X

Access Statistics for this article

Mathematische Nachrichten is currently edited by Robert Denk

More articles in Mathematische Nachrichten from Wiley Blackwell
Bibliographic data for series maintained by Wiley Content Delivery ().