Obstructions to a small hyperbolicity in Helly graphs

DOI10.1016/J.DISC.2018.10.017zbMath1400.05069arXiv1709.02837OpenAlexW2754485863WikidataQ128913543 ScholiaQ128913543MaRDI QIDQ1625787

Heather M. Guarnera, Feodor F. Dragan

Publication date: 29 November 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

hyperbolicityinjective hullstructural propertiesisometric subgraphsHelly graphsKing-gridstructural obstructions

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Related Items (10)

Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Injective hulls of various graph classes ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ Eccentricity terrain of \(\delta\)-hyperbolic graphs ⋮ First-order logic axiomatization of metric graph theory ⋮ Helly groups ⋮ Bootstrap percolation in strong products of graphs ⋮ Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Leanness computation: small values and special graph classes ⋮ Fellow travelers phenomenon present in real-world networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperbolicity and chordality of a graph
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Pseudo-modular graphs
• Easy and hard bottleneck location problems
• Diameter and treewidth in minor-closed graph families
• Domination in quadrangle-free Helly graphs
• Hyperbolic bridged graphs
• Applying clique-decomposition for computing Gromov hyperbolicity
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Six theorems about injective metric spaces
• On the Hyperbolicity of Small-World and Treelike Random Graphs
• INJECTIVE HULLS OF CERTAIN DISCRETE METRIC SPACES AND GROUPS
• Euclidean versus Hyperbolic Congestion in Idealized versus Experimental Networks
• Recognition of $C_4$-Free and 1/2-Hyperbolic Graphs
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Graph minors. II. Algorithmic aspects of tree-width
• 1-Hyperbolic Graphs
• Core congestion is inherent in hyperbolic networks
• Metric Embedding, Hyperbolic Space, and Social Networks
• Cop and Robber Game and Hyperbolicity
• Polynomial bounds for the grid-minor theorem
• Scaled Gromov hyperbolic graphs
• To Approximate Treewidth, Use Treelength!
• Algorithms and Computation
• On the hyperbolicity of chordal graphs

This page was built for publication: Obstructions to a small hyperbolicity in Helly graphs