Spanning trees in hyperbolic graphs

DOI10.1007/S00493-015-3082-2zbMATH Open1399.05033arXiv0910.5605OpenAlexW2162358103MaRDI QIDQ1701351FDOQ1701351

Authors: Matthias Hamann 

Publication date: 22 February 2018

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

spanning treeshyperbolic graphsdisjoint rays

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

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

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)