Obstructions to a small hyperbolicity in Helly graphs

DOI10.1016/J.DISC.2018.10.017MaRDI QIDQ1625787zbMATH OpenOpenAlexWikidataFDO

Authors Feodor F. Dragan, Heather M. Guarnera

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

Helly graphshyperbolicityinjective hullisometric subgraphsKing-gridstructural obstructionsstructural properties

Mathematics Subject Classification ID

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

Abstract: It is known that for every graph $G$ there exists the smallest Helly graph $calH(G)$ into which $G$ isometrically embeds ($calH(G)$ is called the injective hull of $G$) such that the hyperbolicity of $calH(G)$ is equal to the hyperbolicity of $G$. Motivated by this, we investigate structural properties of Helly graphs that govern their hyperbolicity and identify three isometric subgraphs of the King-grid as structural obstructions to a small hyperbolicity in Helly graphs.

Recommendations

• On the hyperbolicity of chordal graphs
• Chordality properties and hyperbolicity on graphs
• 1-Hyperbolic Graphs
• Small values of the hyperbolicity constant in graphs
• Graphs with small hyperbolicity constant

Cites work

• 1-Hyperbolic Graphs
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Algorithms and Computation
• Applying clique-decomposition for computing Gromov hyperbolicity
• Cop and robber game and hyperbolicity
• Core congestion is inherent in hyperbolic networks
• Diameter and treewidth in minor-closed graph families
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Domination in quadrangle-free Helly graphs
• Easy and hard bottleneck location problems
• Euclidean versus hyperbolic congestion in idealized versus experimental networks
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Hyperbolic bridged graphs
• Hyperbolicity and chordality of a graph
• Injective hulls of certain discrete metric spaces and groups.
• Metric embedding, hyperbolic space, and social networks
• Metric graph theory and geometry: a survey
• On the hyperbolicity of chordal graphs
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Polynomial bounds for the grid-minor theorem
• Pseudo-modular graphs
• Recognition of C₄-free and 1/2-hyperbolic graphs
• Scaled Gromov hyperbolic graphs
• Six theorems about injective metric spaces
• To approximate treewidth, use treelength!
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces

Cited in

(11)

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

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

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