Hyperbolic bridged graphs

• Given a connected graph G, we take, as usual, the distance xy 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 delta-hyperbolic, for some 3 : 0, if for all vertices x, y, u, v in G the inequality xy + uv :5 max{xu + yv, xv + yu} + delta 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.

Nyckelord

distance-hereditary graphs

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)