Spanning trees in hyperbolic graphs

DOI10.1007/S00493-015-3082-2MaRDI QIDQ1701351zbMATHOpenAlexFDO

Authors Matthias Hamann

Publication date 22 February 2018

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.5605

zbMATH Keywords

spanning treeshyperbolic graphsdisjoint rays

Mathematics Subject Classification ID

Trees (05C05) Infinite graphs (05C63) Hyperbolic groups and nonpositively curved groups (20F67)

Abstract: In this paper we construct spanning trees in hyperbolic graphs that represent their hyperbolic compactification in a good way: so that the tree has a bounded number of distinct rays to each boundary point. The bound depends only on the (Assouad) dimension of the boundary. As a corollary we sharpen a result of Gromov which says that from every hyperbolic graph with bounded degrees one can construct a tree outside the graph with a continuous surjection from the ends of the tree onto the hyperbolic boundary such that the surjection is finite-to-one. We will construct a tree with these properties inside the hyperbolic graph, which in addition is also a spanning tree of that graph.

Recommendations

• On the tree-likeness of hyperbolic spaces
• Spanning trees of locally finite graphs
• scientific article; zbMATH DE number 1457282
• scientific article; zbMATH DE number 561828
• Infinite connected graphs with no end-preserving spanning trees

Cites work

• scientific article; zbMATH DE number 437296 (Why is no real title available?)
• scientific article; zbMATH DE number 1819875 (Why is no real title available?)
• scientific article; zbMATH DE number 1160328 (Why is no real title available?)
• scientific article; zbMATH DE number 1385418 (Why is no real title available?)
• scientific article; zbMATH DE number 849252 (Why is no real title available?)
• Amenable group actions on infinite graphs
• Asymptotic dimension
• Dirichlet problem at infinity on Gromov hyperbolic metric measure spaces
• Elements of asymptotic geometry
• Embeddings of Gromov hyperbolic spaces
• Embeddings of hyperbolic groups into products of binary trees
• Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant
• Géométrie et théorie des groupes. Les groupes hyperboliques de Gromov. (Geometry and group theory. The hyperbolic groups of Gromov)
• Nagata dimension, quasisymmetric embeddings, and Lipschitz extensions
• Plongements lipschitziens dans ${\bbfR}\sp n$
• Quasi-isometries between graphs and trees
• Random Walks on Infinite Graphs and Groups
• Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
• Symbolic dynamics and hyperbolic groups
• The \(\ell_p\)-cohomology and the conformal dimension of hyperbolic cones
• Wurzelbäume und Kantenorientierungen in Graphen
• Über unendliche Wege in Graphen

Cited in

(9)

• Spanning Trees and Domination in Hypercubes
• Independent spanning trees on folded hyper-stars
• On the spanning tree polyhedron
• Spanning trees in multipartite geometric graphs
• On the tree-likeness of hyperbolic spaces
• Transforming spanning trees and pseudo-triangulations
• A Liouville hyperbolic souvlaki
• Spanning trees on hypercubic lattices and nonorientable surfaces
• Grassmann integral representation for spanning hyperforests

This page was built for publication: Spanning trees in hyperbolic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1701351)