Bow Metrics and Hyperbolicity

Abstract

A ($\hat{I}»,\hat{I}¼$)-bow metric was defined in (Dragan & Ducoffe, 2023) as a far reaching generalization of an $\hat{I}{\pm }_i$-metric (which is equivalent to a ($0,i$)-bow metric). A graph $G=(V,E)$ is said to satisfy ($\hat{I}»,\hat{I}¼$)-bow metric if for every four vertices $u,v,w,x$ of $G$ the following holds: if two shortest paths $P(u,w)$ and $P(v,x)$ share a common shortest subpath $P(v,w)$ of length more than $\hat{I}»$ (that is, they overlap by more than $\hat{I}»$), then the distance between $u$ and $x$ is at least $d_G(u,v)+d_G(v,w)+d_G(w,x)-\hat{I}¼$. ($\hat{I}»,\hat{I}¼$)-Bow metric can also be considered for all geodesic metric spaces. It was shown by Dragan & Ducoffe that every $\hat{I}´$-hyperbolic graph (in fact, every $\hat{I}´$-hyperbolic geodesic metric space) satisfies ($\hat{I}´,2\hat{I}´$)-bow metric. Thus, ($\hat{I}»,\hat{I}¼$)-bow metric is a common generalization of hyperbolicity and of $\hat{I}{\pm }_i$-metric. In this paper, we investigate an intriguing question whether ($\hat{I}»,\hat{I}¼$)-bow metric implies hyperbolicity in graphs. Note that, this is not the case for general geodesic metric spaces as Euclidean spaces satisfy ($0,0$)-bow metric whereas they have unbounded hyperbolicity. We conjecture that, in graphs, ($\hat{I}»,\hat{I}¼$)-bow metric indeed implies hyperbolicity and show that our conjecture is true for several large families of graphs.

23 pages, 4 figures