×

1-hyperbolic graphs. (English) Zbl 1029.05043

Summary: The shortest-path metric \(d\) of a graph \(G=(V,E)\) is called \(\delta\)-hyperbolic if for any four vertices \(u,v,w,x\in X\) the two larger of the three sums \(d(u,v)+d(w,x)\), \(d(u,w)+d(v,x)\), \(d(u,x)+d(v,w)\) differ by at most \(\delta.\) In this paper, we characterize the graphs with 1-hyperbolic metrics in terms of a convexity condition and forbidden isometric subgraphs.

MSC:

05C12 Distance in graphs
05C75 Structural characterization of families of graphs
Full Text: DOI