✦ LIBER ✦

Hyperbolic Bridged Graphs

✍ Scribed by Jack H. Koolen; Vincent Moulton

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 201 KB
Volume: 23
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.2002.0591

No coin nor oath required. For personal study only.

✦ Synopsis

Given a connected graph G, we take, as usual, the distance x y between any two vertices x, y of G to be the length of some geodesic between x and y. The graph G is said to be δ-hyperbolic, for some δ ≥ 0, if for all vertices x, y, u, v in G the inequality

holds, and G is bridged if it contains no finite isometric cycles of length four or more. In this paper, we will show that a finite connected bridged graph is 1-hyperbolic if and only if it does not contain any of a list of six graphs as an isometric subgraph.

📜 SIMILAR VOLUMES

Scaled Gromov hyperbolic graphs

✍ Edmond Jonckheere; Poonsuk Lohsoonthorn; Francis Bonahon 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB

## Abstract In this article, the δ‐hyperbolic concept, originally developed for infinite graphs, is adapted to very large but finite graphs. Such graphs can indeed exhibit properties typical of negatively curved spaces, yet the traditional δ‐hyperbolic concept, which requires existence of an upper

Hyperbolicity and complement of graphs

✍ Sergio Bermudo; José M. Rodríguez; José M. Sigarreta; Eva Tourís 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 280 KB

If X is a geodesic metric space and x 1 , x 2 , x 3 ∈ X , a geodesic triangle T = {x 1 , x 2 , x 3 } is the union of the three geodesics [x 1 x 2 ], [x 2 x 3 ] and [x 3 x 1 ] in X . The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of th

When is the graph product of hyperbolic

When is the graph product of hyperbolic groups hyperbolic?

✍ John Meier 📂 Article 📅 1996 🏛 Springer 🌐 English ⚖ 771 KB

Given a finite simplicial graph G, and an assignment of groups to the vertices of if, the graph product is the free product of the vertex groups modulo relations implying that adjacent vertex groups commute. We use Gromov's link criteria for cubical complexes and techniques of Davis and Moussang to

Bridged graphs and geodesic convexity

✍ Martin Farber 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 588 KB

A graph G is bridged if each cycle C of length at least four contains two vertices whose distance from each other in G is strictly less than that in C. The class of bridged graphs is an extension of the class of chordal (or triangulated) graphs which arises in the study of convexity in graphs. A se

Bridged Graphs Are Cop-Win Graphs: An Al

Bridged Graphs Are Cop-Win Graphs: An Algorithmic Proof

✍ Victor Chepoi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 150 KB

A graph is bridged if it contains no isometric cycles of length greater than three. Anstee and Farber established that bridged graphs are cop-win graphs. According to Nowakowski and Winkler and Quilliot, a graph is a cop-win graph if and only if its vertices admit a linear ordering v 1 , v 2 , ...,

The chromaticity of s-bridge graphs and

The chromaticity of s-bridge graphs and related graphs

✍ Shaoji Xu; Jinjie Liu; Yeehock Peng 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 516 KB